早教吧作业答案频道 -->其他-->
分治法找两数组的中值设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...的网友还看了以下：
x=2y+1和y=2x+1是同一个函数吗?那y=1/2x和x=1/2y呢?说只是自变量不同,本质没 2020-05-13 …
求由曲线Y=1/x和直线y=4x,x=2,y=0所为图形面积?求由曲线Y=1/x和直线y=4x,x 2020-05-16 …
初二数学初请详细解答,谢谢!(2620:47:28)已知方程组x+y=1-a和x-y=3a+5的解 2020-05-20 …
方程组2X+Y=1.5和0.8X+0.6y=1.3（1）,2X+Y=1.5和（2）,0.8X+0. 2020-06-04 …
x^2+y^2-2xy=2x所确定的隐函数y=y(x)的极值2x+2yy'-2y-2xy'=2y' 2020-06-06 …
一组和二组的人数是28人,二组和三组的人数是22人,三组和四组的人数是25人,求1组和4组的人数, 2020-07-11 …
请帮我想想如何用较简便的方法解这题：过直线x+y+1=0和圆x^2+y^2-2x-2y-7=0的交 2020-07-26 …
数学集合填空题{x/x=根号a,a小于25,x属于自然树}=直角坐标平面横轴上的点的坐标组成的集合 2020-07-29 …
在同一坐标系中画出了三个一次函数的图象：y=1-x，y=x+1和y=3x-1（1）求y=1-x和y= 2020-10-31 …
2y-5/y-1和-2y+5/1-y不是一样的数吗,那为什么2y-5/y-1≥0和-2y+5/1-y 2020-11-20 …