早教吧作业答案频道 -->其他-->
分治法找两数组的中值设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...的网友还看了以下:
4个人候选最佳学生要被面试30分钟.每一个要被1号和2号各面试15分钟,1号和2号在不同的房间.面 2020-05-13 …
你能把两个摞在一起的湿玻璃杯分开吗?拿两个同一规格的玻璃杯,把一个放在另一个里面,在套在外面的杯子 2020-05-17 …
在常温常压下,将盛满氯气的一支试管倒立在水槽中,当日光照射一段时间至不再反应为止,试管中最后残留气 2020-05-24 …
将一个充满氯气的试管倒扣在盛水的烧杯中,经长时间光照,直到黄绿色气体变为无色气体,水位不再上升时, 2020-06-05 …
如果说宇宙宇宙一种空间的话,那么还会有别的空间存在吗?会有生命吗?或者说是令一种形式存在这里的空间 2020-06-07 …
因为36<40<49,所以6<40<7.40在连续整数6~7之间.用这种方法你来确定63在哪两个整 2020-06-27 …
试在闭区间0,1与a,b间建立两个双射试在闭区间0,1与a,b(a 2020-07-16 …
在图中,小试管的直径略小于大试管的内径,能在大试管内移动。若在大试管内装满水,然后套入小试管,手拿 2020-07-31 …
在著名的心灵感应试验中,两个试验者A,B分在两个房间,某著名心灵感应使用中,两实验者AB分在两个房间 2020-11-02 …
隔水加热,试管中的水会沸腾吗?取一个烧杯注入半瓶水,再取一支试管加入半管水,将试管放在烧杯中(试管与 2020-12-09 …