33,010
社区成员
发帖
与我相关
我的任务
分享请教高手一个找中间值的算法问题！
设数组A和B都是排好序的并且均有N个元素的数组。要求给出一个O(logN)算法找出A并B（集合运算）的中间值。
...全文
请发表友善的回复…
发表回复
绿色夹克衫 2009-01-19
- 打赏
- 举报
看了一下中位数的定义,好像如果是偶数个元素的话,要取中间两个数的均值。
不知道lz要找的是不是中位数！
另外确实存在中位数只存在于其中一个数组里的情况，不过并不影响按照上面的方法来找中位数，
只是要在二分距离=1的时候作一下处理，假如A[i]偏小而A[i+1]又偏大，那么中位数就在B中，为B[N - i - 1]和B[N - i - 2]的平均数(下标从0开始算)
应该用不着再以A为基准重新找一次。
A = 1 2 3 7 9
B = 2 5 7 9 10
可能还存有7的问题，
A = 1 2 3 9 9
B = 2 5 7 9 10
可能就是更标准一些，用二分在A中找的时候，i=2时(3)偏小,i=3时(9)又偏大，所以中位数为B[1]和B[2]的平均数
[Quote=引用 7 楼 shyli 的回复:]
二分的思想是对的，不过要考虑特殊情况。
即该中位数只在A数组或只在B数组。
上面我给的数据错了。
A = 1 2 3 7 9
B = 2 5 7 9 10
[/Quote]
不知道lz要找的是不是中位数！
另外确实存在中位数只存在于其中一个数组里的情况，不过并不影响按照上面的方法来找中位数，
只是要在二分距离=1的时候作一下处理，假如A[i]偏小而A[i+1]又偏大，那么中位数就在B中，为B[N - i - 1]和B[N - i - 2]的平均数(下标从0开始算)
应该用不着再以A为基准重新找一次。
A = 1 2 3 7 9
B = 2 5 7 9 10
可能还存有7的问题，
A = 1 2 3 9 9
B = 2 5 7 9 10
可能就是更标准一些，用二分在A中找的时候，i=2时(3)偏小,i=3时(9)又偏大，所以中位数为B[1]和B[2]的平均数
[Quote=引用 7 楼 shyli 的回复:]
二分的思想是对的，不过要考虑特殊情况。
即该中位数只在A数组或只在B数组。
上面我给的数据错了。
A = 1 2 3 7 9
B = 2 5 7 9 10
[/Quote]
绿色夹克衫 2009-01-19
- 打赏
- 举报
详细的说起来比较麻烦,lz还是看程序吧!
测试的不太细致,不知道还有什么bug没有
[Quote=引用 8 楼 lanyuandong 的回复:]
哎呀，谢谢各位先，但是大家给的算法我好像都看不懂，干脆我给两个数组，希望各位用你们的算法走一遍
A={1,3,5,7,9}
B={2,4,6,8}
看一下给位的算法是如何找到5的，如果B为{2,4,6,8,10}呢，结果又会如何？
谢谢大家了！
[/Quote]
测试的不太细致,不知道还有什么bug没有
private void button1_Click(object sender, EventArgs e)
{
int[] A = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int[] B = new int[] { 0, 0, 0, 2, 3, 9, 9, 10, 10, 11 };
double median = findMedian(A, B, 0, A.Length - 1);
}
private double findMedian(int[] ArrayA, int[] ArrayB, int startIndex, int endIndex)
{
int length = ArrayA.Length - 1;
int medianIndexA = (startIndex + endIndex) / 2;
int medianIndexB = length - medianIndexA;
//如果到边界了,直接返回边界的均值
if(startIndex == length || endIndex == 0)
return (double)(ArrayA[medianIndexA] + ArrayB[medianIndexB]) / 2;
//如果A的元素在两个B元素中间,或B元素在两个A元素中间,返回四个元素中中间2个的均值
if ((ArrayA[medianIndexA] < ArrayB[medianIndexB] && ArrayA[medianIndexA] >= ArrayB[medianIndexB - 1]) || (ArrayA[medianIndexA] < ArrayB[medianIndexB] && ArrayA[medianIndexA + 1] >= ArrayB[medianIndexB]))
return (double)(Math.Max(ArrayA[medianIndexA], ArrayB[medianIndexB - 1]) + Math.Min(ArrayA[medianIndexA + 1], ArrayB[medianIndexB])) / 2;
//如果=直接返回,说明找到了
if (ArrayA[medianIndexA] == ArrayB[medianIndexB])
return ArrayA[medianIndexA];
else if (ArrayA[medianIndexA] < ArrayB[medianIndexB])
//递归找更大的数
return findMedian(ArrayA, ArrayB, medianIndexA + 1, endIndex);
else
//递归找更小的数
return findMedian(ArrayA, ArrayB, startIndex, medianIndexA - 1);
}
[Quote=引用 8 楼 lanyuandong 的回复:]
哎呀，谢谢各位先，但是大家给的算法我好像都看不懂，干脆我给两个数组，希望各位用你们的算法走一遍
A={1,3,5,7,9}
B={2,4,6,8}
看一下给位的算法是如何找到5的，如果B为{2,4,6,8,10}呢，结果又会如何？
谢谢大家了！
[/Quote]
na2650945 2009-01-18
- 打赏
- 举报
[Quote=引用 5 楼 litaoye 的回复:]
我上面说的应该没错吧！可能就是计数用的方式不太一样，不过从0开始计也可以找到5
中值为4,4在A中排第4,在B中排5-4 = 1,如果从0开始计，中值为5，在A中排第4，B中排第5-4 = 1
按照我给出的方法可能找不到4,但肯定能找到5
(这道题中值应当为4\5),找到4要向后取到5,找到5也要向前取到4
二分过程为先找到3和10,3 < 10,所以中位数是大于3小于10的,A向后二分找,B向前二分找,找到4和5,
4小于5,A继续向前二分,B继续向后…
[/Quote]
小学习下思想。
我上面说的应该没错吧！可能就是计数用的方式不太一样，不过从0开始计也可以找到5
中值为4,4在A中排第4,在B中排5-4 = 1,如果从0开始计，中值为5，在A中排第4，B中排第5-4 = 1
按照我给出的方法可能找不到4,但肯定能找到5
(这道题中值应当为4\5),找到4要向后取到5,找到5也要向前取到4
二分过程为先找到3和10,3 < 10,所以中位数是大于3小于10的,A向后二分找,B向前二分找,找到4和5,
4小于5,A继续向前二分,B继续向后…
[/Quote]
小学习下思想。
lanyuandong 2009-01-18
- 打赏
- 举报
不好意思，搞错了，B应该与A有相同的元素，那么共有2N个元素，如果元素都不相同那么是不是就没有中位数呀？
lanyuandong 2009-01-18
- 打赏
- 举报
哎呀，谢谢各位先，但是大家给的算法我好像都看不懂，干脆我给两个数组，希望各位用你们的算法走一遍
A={1,3,5,7,9}
B={2,4,6,8}
看一下给位的算法是如何找到5的，如果B为{2,4,6,8,10}呢，结果又会如何？
谢谢大家了！
A={1,3,5,7,9}
B={2,4,6,8}
看一下给位的算法是如何找到5的，如果B为{2,4,6,8,10}呢，结果又会如何？
谢谢大家了！
shyli 2009-01-18
- 打赏
- 举报
二分的思想是对的，不过要考虑特殊情况。
即该中位数只在A数组或只在B数组。
上面我给的数据错了。
A = 1 2 3 7 9
B = 2 5 7 9 10
即该中位数只在A数组或只在B数组。
上面我给的数据错了。
A = 1 2 3 7 9
B = 2 5 7 9 10
shyli 2009-01-18
- 打赏
- 举报
[Quote=引用 2 楼 litaoye 的回复:]
假设这个中位数在A中的位置为p,那么他在B中的位置一定是N-p,实际上就是用二分法找到这个p,
在A中找,然后在B中验证是否处于N-p的位置,
如果A[i] == B[N-i] 则p = i
或
正序时 (A[i] > B[N-i] 且 A[i] < B[N-i + 1]) 则p = i
倒序时 (A[i] < B[N-i] 且 A[i] > B[N-i + 1]) 则p = i
[/Quote]
中位数未必在两个数组中都有啊。
比如
A = 1 2 3 7
B = 2 5 7 9 10
中位数是5
假设这个中位数在A中的位置为p,那么他在B中的位置一定是N-p,实际上就是用二分法找到这个p,
在A中找,然后在B中验证是否处于N-p的位置,
如果A[i] == B[N-i] 则p = i
或
正序时 (A[i] > B[N-i] 且 A[i] < B[N-i + 1]) 则p = i
倒序时 (A[i] < B[N-i] 且 A[i] > B[N-i + 1]) 则p = i
[/Quote]
中位数未必在两个数组中都有啊。
比如
A = 1 2 3 7
B = 2 5 7 9 10
中位数是5
绿色夹克衫 2009-01-18
- 打赏
- 举报
我上面说的应该没错吧！可能就是计数用的方式不太一样，不过从0开始计也可以找到5
中值为4,4在A中排第4,在B中排5-4 = 1,如果从0开始计，中值为5，在A中排第4，B中排第5-4 = 1
按照我给出的方法可能找不到4,但肯定能找到5
(这道题中值应当为4\5),找到4要向后取到5,找到5也要向前取到4
二分过程为先找到3和10,3 < 10,所以中位数是大于3小于10的,A向后二分找,B向前二分找,找到4和5,
4小于5,A继续向前二分,B继续向后二分,找到5和4,5>4 且5 <= 4后面的5,所以p = 5,然后再比较一下临近的
几个值,找到4。
应该算是比较标准的O(logN)
[Quote=引用 4 楼 fengxiquan 的回复:]
这个问题分3类比较简单一点
1.区间不相交;
2.区间包含;
3.区间部分相交;
2.3.都应该对相交区间元素排序(注意:可能有相等元素),再寻找恰当的值(中值)
楼上的说法("假设这个中位数在A中的位置为p,那么他在B中的位置一定是N-p")是错误的
比如: A = {1,2,3,4,5}
B = {4,5,10,100,1000}
中值为4, A的位置是3, B的位置在0.
但楼上的思路是对的,这是二分的推广.这比上面的3类分,排序复杂度小,但难于理…
[/Quote]
中值为4,4在A中排第4,在B中排5-4 = 1,如果从0开始计，中值为5，在A中排第4，B中排第5-4 = 1
按照我给出的方法可能找不到4,但肯定能找到5
(这道题中值应当为4\5),找到4要向后取到5,找到5也要向前取到4
二分过程为先找到3和10,3 < 10,所以中位数是大于3小于10的,A向后二分找,B向前二分找,找到4和5,
4小于5,A继续向前二分,B继续向后二分,找到5和4,5>4 且5 <= 4后面的5,所以p = 5,然后再比较一下临近的
几个值,找到4。
应该算是比较标准的O(logN)
[Quote=引用 4 楼 fengxiquan 的回复:]
这个问题分3类比较简单一点
1.区间不相交;
2.区间包含;
3.区间部分相交;
2.3.都应该对相交区间元素排序(注意:可能有相等元素),再寻找恰当的值(中值)
楼上的说法("假设这个中位数在A中的位置为p,那么他在B中的位置一定是N-p")是错误的
比如: A = {1,2,3,4,5}
B = {4,5,10,100,1000}
中值为4, A的位置是3, B的位置在0.
但楼上的思路是对的,这是二分的推广.这比上面的3类分,排序复杂度小,但难于理…
[/Quote]
FancyMouse 2009-01-17
- 打赏
- 举报
A交B为空么？
fengxiquan 2009-01-17
- 打赏
- 举报
这个问题分3类比较简单一点
1.区间不相交;
2.区间包含;
3.区间部分相交;
2.3.都应该对相交区间元素排序(注意:可能有相等元素),再寻找恰当的值(中值)
楼上的说法("假设这个中位数在A中的位置为p,那么他在B中的位置一定是N-p")是错误的
比如: A = {1,2,3,4,5}
B = {4,5,10,100,1000}
中值为4, A的位置是3, B的位置在0.
但楼上的思路是对的,这是二分的推广.这比上面的3类分,排序复杂度小,但难于理解
1.区间不相交;
2.区间包含;
3.区间部分相交;
2.3.都应该对相交区间元素排序(注意:可能有相等元素),再寻找恰当的值(中值)
楼上的说法("假设这个中位数在A中的位置为p,那么他在B中的位置一定是N-p")是错误的
比如: A = {1,2,3,4,5}
B = {4,5,10,100,1000}
中值为4, A的位置是3, B的位置在0.
但楼上的思路是对的,这是二分的推广.这比上面的3类分,排序复杂度小,但难于理解
chenyingshu 2009-01-17
- 打赏
- 举报
[Quote=引用 2 楼 litaoye 的回复:]
假设这个中位数在A中的位置为p,那么他在B中的位置一定是N-p,实际上就是用二分法找到这个p,
在A中找,然后在B中验证是否处于N-p的位置,
如果A[i] == B[N-i] 则p = i
或
正序时 (A[i] > B[N-i] 且 A[i] < B[N-i + 1]) 则p = i
倒序时 (A[i] < B[N-i] 且 A[i] > B[N-i + 1]) 则p = i
[/Quote]
我也是这样认为的
假设这个中位数在A中的位置为p,那么他在B中的位置一定是N-p,实际上就是用二分法找到这个p,
在A中找,然后在B中验证是否处于N-p的位置,
如果A[i] == B[N-i] 则p = i
或
正序时 (A[i] > B[N-i] 且 A[i] < B[N-i + 1]) 则p = i
倒序时 (A[i] < B[N-i] 且 A[i] > B[N-i + 1]) 则p = i
[/Quote]
我也是这样认为的
绿色夹克衫 2009-01-17
- 打赏
- 举报
假设这个中位数在A中的位置为p,那么他在B中的位置一定是N-p,实际上就是用二分法找到这个p,
在A中找,然后在B中验证是否处于N-p的位置,
如果A[i] == B[N-i] 则p = i
或
正序时 (A[i] > B[N-i] 且 A[i] < B[N-i + 1]) 则p = i
倒序时 (A[i] < B[N-i] 且 A[i] > B[N-i + 1]) 则p = i
在A中找,然后在B中验证是否处于N-p的位置,
如果A[i] == B[N-i] 则p = i
或
正序时 (A[i] > B[N-i] 且 A[i] < B[N-i + 1]) 则p = i
倒序时 (A[i] < B[N-i] 且 A[i] > B[N-i + 1]) 则p = i
