早教吧作业答案频道 -->其他-->
分治法找两数组的中值设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...的网友还看了以下：
PID调节中的微分时间与积分时间的作用PID调节中微分时间和积分时间各起到什么作用?怎么计算这两个 2020-05-17 …
在9点多少分,时针和分针在10的两侧,并且到10的距离相等?请尽可能详细地回答吧!最好用算术方法, 2020-05-19 …
对于一维扩散问题,写出相应的微分方程和差分方程材料模拟与计算 2020-05-24 …
1.上午10点整,时针和分针成几度角?2.午上1.上午10点整,时针和分针成几度角?2.上午7时5 2020-06-15 …
一、1.8时25分,时针和分针的夹角是多少度?（顺时针方向讨论）2.4时40分,时针和分针的夹角是 2020-07-12 …
钟面上3时过多少分,时针和分针离3的距离相等,并且在3的两边?求每步解释,要详细~~已知答案为：解 2020-07-17 …
微分方程和代数方程的定义有什么不同?还有：当把微分方程的表达式都移到等式的一边,再把零和等号去掉, 2020-07-31 …
可降阶的二阶微分方程和二阶常系数线性微分方程的区别这两种类型的方程如何区别呢我现在总是搞不清微分方 2020-08-02 …
初一平行线2点20分,时针和分针所成的角是（）如果钟面上时针和分针恰成90°的角,那么时针所指的时候 2020-11-03 …
高数,常微分方程中的问题~全书上说,在用可分离的微分方程和齐次方程时,因为要用到除法,可能会失去解, 2020-11-03 …