早教吧作业答案频道 -->其他-->
分治法找两数组的中值设X[1..n]和Y[1..n]是两个有序数组,试设计运行时间为O(1bn)的算法,找出在数组X和Y中的2n个元素的中值.请给出完整的程序。
题目详情
分治法找两数组的中值
设X[1..n]和Y[1..n]是两个有序数组,试设计运行时间为O(1b n)的算法,找出在数组X和Y中的2n个元素的中值.
请给出完整的程序。
设X[1..n]和Y[1..n]是两个有序数组,试设计运行时间为O(1b n)的算法,找出在数组X和Y中的2n个元素的中值.
请给出完整的程序。
▼优质解答
答案和解析
这个就在教科书上阿.参考算法导论
很长的哦：
C#的,这个是计算第K个数的,令K=n/2就行了
using System;
using System.Collections;
using NUnit.Framework;
using Algorithm.Test;
namespace Algorithm.Select
{
///
/// Kth_Samllest_Selection 的摘要说明.
///
public class Kth_Samllest_Selection
{
ArrayList m_al;
ArrayList m_MedianAl;
ArrayList m_S1;
ArrayList m_S2;
int m_K;
public Kth_Samllest_Selection(ArrayList al,int K)
{
m_al = al;
m_K = K;
m_MedianAl = new ArrayList(al.Count/5+1);
m_S1 = new ArrayList(al.Count/2);
m_S2 = new ArrayList(al.Count/2);
}
///
/// 执行操作
///
///第K个数的大小
public int Do()
{
if(m_al.Count<=5)
{
m_al.Sort();
return ((ComparableObject)m_al[m_K-1]).Value;
}
while(m_al.Count%5!=0)
{
m_al.Add(new ComparableObject(int.MaxValue));
}
int k = m_al.Count/5;
for(int i=0;i
int start = i*5;
int num1 = ((ComparableObject)m_al[start]).Value;
int num2 = ((ComparableObject)m_al[start+1]).Value;
int num3 = ((ComparableObject)m_al[start+2]).Value;
int num4 = ((ComparableObject)m_al[start+3]).Value;
int num5 = ((ComparableObject)m_al[start+4]).Value;
MakeMedianNumMiddle(ref num1,ref num2,ref num3,ref num4,ref num5);
((ComparableObject)m_al[start]).Value = num1;
((ComparableObject)m_al[start+1]).Value= num2;
((ComparableObject)m_al[start+2]).Value= num3;
((ComparableObject)m_al[start+3]).Value= num4;
((ComparableObject)m_al[start+4]).Value= num5;
m_MedianAl.Add((ComparableObject)num3);
//m_MedianAl.Add((MakeMedianNumMiddle(ref (ComparableObject)m_al[start],ref (ComparableObject)m_al[start+1],ref (ComparableObject)m_al[start+2],ref (ComparableObject)m_al[start+3],ref (ComparableObject)m_al[start+4]))[2]);
}
Kth_Samllest_Selection selector = new Kth_Samllest_Selection(m_MedianAl,m_MedianAl.Count/2);
int tmp = selector.Do();
m_MedianAl.Clear();
m_MedianAl = null;
for(int i=0;i
int start = i*5;
if(((ComparableObject)m_al[start+2]).Value
m_S1.Add((ComparableObject)m_al[start+0]);
m_S1.Add(m_al[start+1]);
m_S1.Add(m_al[start+2]);
if(((ComparableObject)m_al[start+3]).Value
m_S1.Add(m_al[start+3]);
}
else
{
m_S2.Add(m_al[start+3]);
}
if(((ComparableObject)m_al[start+4]).Value
m_S1.Add(m_al[start+4]);
}
else
{
m_S2.Add(m_al[start+4]);
}
}
else
{
m_S2.Add(m_al[start+2]);
m_S2.Add(m_al[start+3]);
m_S2.Add(m_al[start+4]);
if(((ComparableObject)m_al[start]).Value>tmp)
{
m_S2.Add(m_al[start]);
}
else
{
m_S1.Add(m_al[start+0]);
}
if(((ComparableObject)m_al[start+1]).Value>tmp)
{
m_S2.Add(m_al[start+1]);
}
else
{
m_S1.Add(m_al[start+1]);
}
}
}
///System.Threading.Thread.Sleep(5);
if(m_S1.Count+1==m_K)
{
return tmp;
}
else if(m_K<=m_S1.Count)
{
Kth_Samllest_Selection selector1 = new Kth_Samllest_Selection(m_S1,m_K);
m_S2.Clear();
m_S2 = null;
int ret = selector1.Do();
selector1 = null;
return ret;
}
else
{
Kth_Samllest_Selection selector2 = new Kth_Samllest_Selection(m_S2,m_K-m_S1.Count);
m_S1.Clear();
m_S1 = null;
int ret = selector2.Do();
selector2 = null;
return ret;
}
}
//最多比较6次可以在5个数中找到中位数
public void MakeMedianNumMiddle(ref int num1,ref int num2,ref int num3,ref int num4,ref int num5)
{
//-------------------------------------------------------------------
if(num2.CompareTo(num1)<0)//num1 存放小数
{
Exchange(ref num1,ref num2);
}
if(num4.CompareTo(num3)<0)//num3 存放小数
{
Exchange(ref num3,ref num4);
}
// 1 3 5
// / /
// 2 4
//---------------------------------------------------------------------
if(num3.CompareTo(num1)<0)//num1 存放小数
{
Exchange(ref num1,ref num3);
Exchange(ref num2,ref num4);
}
//--------------------before here compare three times
//--------------------after here compare at most four times
// 1 5
// / \
// 2 3
// /
// 4
//---------------------------------------------------------------------
if(num2.CompareTo(num5)<0)
{
#region compare two times 12354
// 1
// / \
// 2 3
// / \
// 5 4
//--------------------------------------------------------------------
if(num2.CompareTo(num3)<0)
{
#region compare once 15234
// 1
// /
// 2
// / \
// 5 3
// \
// 4
//--------------------------------------------------------------------
if(num5.CompareTo(num3)<0)
{
// 1
// |
// 2
// |
// 5
// |
// 3
// |
// 4
Exchange(ref num3,ref num5);
}
else
{
// 1
// \
// 2
// \
// 3
// / \
// 5 4
//--------------------------------------------------------------------
}
#endregion
}
else
{
#region compare once 15234
// 1
// /
// 3
// / \
// 4 2
// \
// 5
//--------------------------------------------------------------------
if(num2.CompareTo(num4)<0)
{
// 1
// \
// 3
// \
// 2
// / \
// 4 5
//--------------------------------------------------------------------
Exchange(ref num3,ref num2);
}
else
{
// 1
// \
// 3
// \
// 4
// \
// 2
// \
// 5
//--------------------------------------------------------------------
Exchange(ref num3,ref num4);
Exchange(ref num4,ref num2);
}
#endregion
}
#endregion
}
else
{
#region compare two times 15432
// 5 1
// \ / \
// 2 3
// /
// 4
//--------------------------------------------------------------------
if(num5.CompareTo(num3)<0)
{
#region compare once 12345
// 5 1
// |\/|
// 2 3
// |
// 4
//--------------------------------------------------------------------
if(num2.CompareTo(num3)<0)
{
// 5 1
// | /
// 2
// \
// 3
// |
// 4
//--------------------------------------------------------------------
Exchange(ref num3,ref num2);
Exchange(ref num2,ref num5);
}
else
{
// 5 1
// \|
// 3
// /|
// 2 4
//--------------------------------------------------------------------
Exchange(ref num2,ref num5);
}
#endregion
}
else
{
#region compare once 13245
// 1
// |
// 3
// / \
// 4 5
// \
// 2
if(num4.CompareTo(num5)<0)
{
// 1
// |
// 3
// |
// 4
// |
// 5
// |
// 2
Exchange(ref num3,ref num4);
Exchange(ref num2,ref num4);
}
else
{
// 1
// |
// 3
// |
// 5
// / \
// 4 2
//
//
Exchange(ref num3,ref num5);
Exchange(ref num5,ref num2);
}
#endregion
}
#endregion
}
}
private void Exchange(ref int obj1,ref int obj2)
{
int tmp = obj2;
obj2 = obj1;
obj1 =tmp;
}
}
#region Unit Test
[TestFixture]
[Category("Select")]
public class TestKth_Samllest_Selection
{
ArrayList m_array1;
public TestKth_Samllest_Selection()
{
m_array1 = null;
}
[TestFixtureSetUp]
public void Init()
{
m_array1 = new ArrayList(2000001);
for(int i=0;i<2000000;++i)
{
m_array1.Add(new ComparableObject(new System.Random().Next(2000000)));
}
// for(int i=0;i<25;++i)
// {
// m_array1.Add(new ComparableObject(i+1));
// }
// m_array1.Add(new ComparableObject(1));
// m_array1.Add(new ComparableObject(20));
// m_array1.Add(new ComparableObject(3));
// m_array1.Add(new ComparableObject(14));
// m_array1.Add(new ComparableObject(25));
// m_array1.Add(new ComparableObject(6));
// m_array1.Add(new ComparableObject(10));
// m_array1.Add(new ComparableObject(8));
// m_array1.Add(new ComparableObject(9));
// m_array1.Add(new ComparableObject(7));
// m_array1.Add(new ComparableObject(11));
// m_array1.Add(new ComparableObject(12));
// m_array1.Add(new ComparableObject(24));
// m_array1.Add(new ComparableObject(4));
// m_array1.Add(new ComparableObject(15));
// m_array1.Add(new ComparableObject(16));
// m_array1.Add(new ComparableObject(17));
// m_array1.Add(new ComparableObject(18));
// m_array1.Add(new ComparableObject(19));
// m_array1.Add(new ComparableObject(2));
// m_array1.Add(new ComparableObject(21));
// m_array1.Add(new ComparableObject(22));
// m_array1.Add(new ComparableObject(23));
// m_array1.Add(new ComparableObject(13));
// m_array1.Add(new ComparableObject(5));
// for(int i=0;i<10000;++i)
// {
// m_array1.Add(new ComparableObject(new System.Random().Next(100,1000)));
// }
}
[Test]
public void test()
{
long tmp = DateTime.Now.Ticks;
Kth_Samllest_Selection selector = new Kth_Samllest_Selection(m_array1,1000000);
Console.WriteLine(selector.Do());
Console.WriteLine((DateTime.Now.Ticks-tmp)/6000000.0);
//ArrayList ret = selector.MakeMedianNumMiddle(new ComparableObject(5),
// new ComparableObject(4),
// new ComparableObject(2),
// new ComparableObject(3),
// new ComparableObject(1));
//foreach(ComparableObject item in ret)
//{
// Console.WriteLine(item);
//}
Console.ReadLine();
}
public static void Main()
{
TestKth_Samllest_Selection tester = new TestKth_Samllest_Selection();
tester.Init();
tester.test();
}
}
#endregion
}
很长的哦：
C#的,这个是计算第K个数的,令K=n/2就行了
using System;
using System.Collections;
using NUnit.Framework;
using Algorithm.Test;
namespace Algorithm.Select
{
///
/// Kth_Samllest_Selection 的摘要说明.
///
public class Kth_Samllest_Selection
{
ArrayList m_al;
ArrayList m_MedianAl;
ArrayList m_S1;
ArrayList m_S2;
int m_K;
public Kth_Samllest_Selection(ArrayList al,int K)
{
m_al = al;
m_K = K;
m_MedianAl = new ArrayList(al.Count/5+1);
m_S1 = new ArrayList(al.Count/2);
m_S2 = new ArrayList(al.Count/2);
}
///
/// 执行操作
///
///
public int Do()
{
if(m_al.Count<=5)
{
m_al.Sort();
return ((ComparableObject)m_al[m_K-1]).Value;
}
while(m_al.Count%5!=0)
{
m_al.Add(new ComparableObject(int.MaxValue));
}
int k = m_al.Count/5;
for(int i=0;i
int start = i*5;
int num1 = ((ComparableObject)m_al[start]).Value;
int num2 = ((ComparableObject)m_al[start+1]).Value;
int num3 = ((ComparableObject)m_al[start+2]).Value;
int num4 = ((ComparableObject)m_al[start+3]).Value;
int num5 = ((ComparableObject)m_al[start+4]).Value;
MakeMedianNumMiddle(ref num1,ref num2,ref num3,ref num4,ref num5);
((ComparableObject)m_al[start]).Value = num1;
((ComparableObject)m_al[start+1]).Value= num2;
((ComparableObject)m_al[start+2]).Value= num3;
((ComparableObject)m_al[start+3]).Value= num4;
((ComparableObject)m_al[start+4]).Value= num5;
m_MedianAl.Add((ComparableObject)num3);
//m_MedianAl.Add((MakeMedianNumMiddle(ref (ComparableObject)m_al[start],ref (ComparableObject)m_al[start+1],ref (ComparableObject)m_al[start+2],ref (ComparableObject)m_al[start+3],ref (ComparableObject)m_al[start+4]))[2]);
}
Kth_Samllest_Selection selector = new Kth_Samllest_Selection(m_MedianAl,m_MedianAl.Count/2);
int tmp = selector.Do();
m_MedianAl.Clear();
m_MedianAl = null;
for(int i=0;i
int start = i*5;
if(((ComparableObject)m_al[start+2]).Value
m_S1.Add((ComparableObject)m_al[start+0]);
m_S1.Add(m_al[start+1]);
m_S1.Add(m_al[start+2]);
if(((ComparableObject)m_al[start+3]).Value
m_S1.Add(m_al[start+3]);
}
else
{
m_S2.Add(m_al[start+3]);
}
if(((ComparableObject)m_al[start+4]).Value
m_S1.Add(m_al[start+4]);
}
else
{
m_S2.Add(m_al[start+4]);
}
}
else
{
m_S2.Add(m_al[start+2]);
m_S2.Add(m_al[start+3]);
m_S2.Add(m_al[start+4]);
if(((ComparableObject)m_al[start]).Value>tmp)
{
m_S2.Add(m_al[start]);
}
else
{
m_S1.Add(m_al[start+0]);
}
if(((ComparableObject)m_al[start+1]).Value>tmp)
{
m_S2.Add(m_al[start+1]);
}
else
{
m_S1.Add(m_al[start+1]);
}
}
}
///System.Threading.Thread.Sleep(5);
if(m_S1.Count+1==m_K)
{
return tmp;
}
else if(m_K<=m_S1.Count)
{
Kth_Samllest_Selection selector1 = new Kth_Samllest_Selection(m_S1,m_K);
m_S2.Clear();
m_S2 = null;
int ret = selector1.Do();
selector1 = null;
return ret;
}
else
{
Kth_Samllest_Selection selector2 = new Kth_Samllest_Selection(m_S2,m_K-m_S1.Count);
m_S1.Clear();
m_S1 = null;
int ret = selector2.Do();
selector2 = null;
return ret;
}
}
//最多比较6次可以在5个数中找到中位数
public void MakeMedianNumMiddle(ref int num1,ref int num2,ref int num3,ref int num4,ref int num5)
{
//-------------------------------------------------------------------
if(num2.CompareTo(num1)<0)//num1 存放小数
{
Exchange(ref num1,ref num2);
}
if(num4.CompareTo(num3)<0)//num3 存放小数
{
Exchange(ref num3,ref num4);
}
// 1 3 5
// / /
// 2 4
//---------------------------------------------------------------------
if(num3.CompareTo(num1)<0)//num1 存放小数
{
Exchange(ref num1,ref num3);
Exchange(ref num2,ref num4);
}
//--------------------before here compare three times
//--------------------after here compare at most four times
// 1 5
// / \
// 2 3
// /
// 4
//---------------------------------------------------------------------
if(num2.CompareTo(num5)<0)
{
#region compare two times 12354
// 1
// / \
// 2 3
// / \
// 5 4
//--------------------------------------------------------------------
if(num2.CompareTo(num3)<0)
{
#region compare once 15234
// 1
// /
// 2
// / \
// 5 3
// \
// 4
//--------------------------------------------------------------------
if(num5.CompareTo(num3)<0)
{
// 1
// |
// 2
// |
// 5
// |
// 3
// |
// 4
Exchange(ref num3,ref num5);
}
else
{
// 1
// \
// 2
// \
// 3
// / \
// 5 4
//--------------------------------------------------------------------
}
#endregion
}
else
{
#region compare once 15234
// 1
// /
// 3
// / \
// 4 2
// \
// 5
//--------------------------------------------------------------------
if(num2.CompareTo(num4)<0)
{
// 1
// \
// 3
// \
// 2
// / \
// 4 5
//--------------------------------------------------------------------
Exchange(ref num3,ref num2);
}
else
{
// 1
// \
// 3
// \
// 4
// \
// 2
// \
// 5
//--------------------------------------------------------------------
Exchange(ref num3,ref num4);
Exchange(ref num4,ref num2);
}
#endregion
}
#endregion
}
else
{
#region compare two times 15432
// 5 1
// \ / \
// 2 3
// /
// 4
//--------------------------------------------------------------------
if(num5.CompareTo(num3)<0)
{
#region compare once 12345
// 5 1
// |\/|
// 2 3
// |
// 4
//--------------------------------------------------------------------
if(num2.CompareTo(num3)<0)
{
// 5 1
// | /
// 2
// \
// 3
// |
// 4
//--------------------------------------------------------------------
Exchange(ref num3,ref num2);
Exchange(ref num2,ref num5);
}
else
{
// 5 1
// \|
// 3
// /|
// 2 4
//--------------------------------------------------------------------
Exchange(ref num2,ref num5);
}
#endregion
}
else
{
#region compare once 13245
// 1
// |
// 3
// / \
// 4 5
// \
// 2
if(num4.CompareTo(num5)<0)
{
// 1
// |
// 3
// |
// 4
// |
// 5
// |
// 2
Exchange(ref num3,ref num4);
Exchange(ref num2,ref num4);
}
else
{
// 1
// |
// 3
// |
// 5
// / \
// 4 2
//
//
Exchange(ref num3,ref num5);
Exchange(ref num5,ref num2);
}
#endregion
}
#endregion
}
}
private void Exchange(ref int obj1,ref int obj2)
{
int tmp = obj2;
obj2 = obj1;
obj1 =tmp;
}
}
#region Unit Test
[TestFixture]
[Category("Select")]
public class TestKth_Samllest_Selection
{
ArrayList m_array1;
public TestKth_Samllest_Selection()
{
m_array1 = null;
}
[TestFixtureSetUp]
public void Init()
{
m_array1 = new ArrayList(2000001);
for(int i=0;i<2000000;++i)
{
m_array1.Add(new ComparableObject(new System.Random().Next(2000000)));
}
// for(int i=0;i<25;++i)
// {
// m_array1.Add(new ComparableObject(i+1));
// }
// m_array1.Add(new ComparableObject(1));
// m_array1.Add(new ComparableObject(20));
// m_array1.Add(new ComparableObject(3));
// m_array1.Add(new ComparableObject(14));
// m_array1.Add(new ComparableObject(25));
// m_array1.Add(new ComparableObject(6));
// m_array1.Add(new ComparableObject(10));
// m_array1.Add(new ComparableObject(8));
// m_array1.Add(new ComparableObject(9));
// m_array1.Add(new ComparableObject(7));
// m_array1.Add(new ComparableObject(11));
// m_array1.Add(new ComparableObject(12));
// m_array1.Add(new ComparableObject(24));
// m_array1.Add(new ComparableObject(4));
// m_array1.Add(new ComparableObject(15));
// m_array1.Add(new ComparableObject(16));
// m_array1.Add(new ComparableObject(17));
// m_array1.Add(new ComparableObject(18));
// m_array1.Add(new ComparableObject(19));
// m_array1.Add(new ComparableObject(2));
// m_array1.Add(new ComparableObject(21));
// m_array1.Add(new ComparableObject(22));
// m_array1.Add(new ComparableObject(23));
// m_array1.Add(new ComparableObject(13));
// m_array1.Add(new ComparableObject(5));
// for(int i=0;i<10000;++i)
// {
// m_array1.Add(new ComparableObject(new System.Random().Next(100,1000)));
// }
}
[Test]
public void test()
{
long tmp = DateTime.Now.Ticks;
Kth_Samllest_Selection selector = new Kth_Samllest_Selection(m_array1,1000000);
Console.WriteLine(selector.Do());
Console.WriteLine((DateTime.Now.Ticks-tmp)/6000000.0);
//ArrayList ret = selector.MakeMedianNumMiddle(new ComparableObject(5),
// new ComparableObject(4),
// new ComparableObject(2),
// new ComparableObject(3),
// new ComparableObject(1));
//foreach(ComparableObject item in ret)
//{
// Console.WriteLine(item);
//}
Console.ReadLine();
}
public static void Main()
{
TestKth_Samllest_Selection tester = new TestKth_Samllest_Selection();
tester.Init();
tester.test();
}
}
#endregion
}
看了 分治法找两数组的中值设X[1...的网友还看了以下：
完全归纳法证明相等∑j=n/2(n+1),j=1到n,这个是提前给出的,可以不用证明在接下来的完全 2020-04-27 …
1/2{1/2［1/2(1/2y-3)-3］-3}=17x-1/0.024=1-0.2x/0.08 2020-04-27 …
(1)1/1*2+1/2*3+.+1/2009*2010(2)1/2*4+1/4*6+.+1/20 2020-05-17 …
化简：（a-1)(a+1)(a2+1)(1/3+a)(1/3-a)(1/9+a2)(4+y2)(2 2020-05-22 …
话题作文的题目,完整的开头结尾和内容梗概.格式：以**为话题的作文《*****》（题目）开头：.（ 2020-07-06 …
(1/2+1/3+1/4+...1/2013)X(1+1/2+1/3+1/4+...1/2012) 2020-07-14 …
甲组的4名工人3月份完成的总量比此月人均定额的4倍多20件,乙组的5名工人三月份的工作比此月的人均 2020-07-20 …
已知数列{an}得通项公式an=1/n+1+1/n+2+1/n+3+...+1/2n(n∈n*). 2020-07-26 …
求一道预备班数学期中考试的答案小明在做题时发现了一个规律：1*2/1=1-2/1,2*3/1=2/1 2020-11-05 …
高中数学抽象函数已知定义在(-1,1)上的函数f(x)满足f(1/2)=1,且对任意x,y∈(-1, 2020-12-08 …