寻找中位数 |
在两个长度相等的排序数组中找到上中位数
【题目】
给定两个有序数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。要求时 间复杂度O(logN)，空间复杂度O(1）
【举例】
例如 arr1 = [1, 2,3,4]，arr2 = [3,4,5,6]。
总共8个数，则中位数就是第 4 小的数，为 3.
例如 arr1 = [0,1,2]，arr2 = [3,4,5]。
总共6个数，则中位数就是第 3 小的数，为 2.
解
当N为偶数
假定 arr1 = [1, 2,3,4]，arr2 = [3,4,5,6]。
则数组的长度为 n =4。
分别选出这两个数组的上中位数的下标，即
- mid1 = (n-1)/2 = 1。
- mid2 = (n - 1)/2 = 1。
假如 arr2[mid2] > arr1[mid1]，那么我们要找的目标数是一定存在于 arr1[mid1+1...n] 和arr2[0...mid2]中。而不可能存在于 arr1[0...mid1] 和 arr2[mid2+1...n] 之中。（否则一定存在于arr2[mid2+1,n]和arr1[0,mid]之中）
为什么呢？
因为如当arr1[mid1]<arr2[mid2]时，arr1[0:mid1]必然太小了（较中位数），中位数不可能在这里面；而arr2[mid2,N]则必然太大了，中位数也不可能在这里面。（关键就在于mid，mid把一个数组分成了两半，则实际上是把两个数组分成了三段，一段是arr1[0,mid1],一段是arr1[mid1+1]到arr2[0,mid2]，一段是arr2[mid2+1,n]，那么显然只要arr1[mid1+1]到arr2[0,mid2]之间至少有一个元素，那么中位数肯定就在这个区间里面（而当这个区域只剩下一个元素或者两个元素时，我们就得到了答案）。）
而当arr1[mid1]==arr2[mid2]时，则arr1[mid1]（或者arr2[mid2]）就是中位数。
想象一下，mid1和mid2分别把arr1和arr2分成了两半，那么当arr1[mid1]==arr2[mid2]时，则arr1的mid1的左边的数量等于arr2的mid2的左边的数量，右边也是如此，故这个就是中位数。
干脆画出来吧(把这两个数组可能的重叠情况（两个数组的相对排序情况，基于arr2[mid2]>arr1[mid1]）画出来)：
除了第六条两数组不重叠之外，下面五条中，可以轻易的发现，当arr1[mid1]==arr2[mid2]时
必然这个数就是中位数，所以，中位数必然是在arr1[mid1，n]和arr2[0,mid2]中间
（反过来也是一样的道理）。
这下总该懂了吧。
1
------
------
2
------
------
3
------
------
4
------
------
5
------
------
6（arr2[0]>arr1[n],就对应了最终return Math.min(arr1[l1], arr2[l2])；这一句，当然，
看题目要求，也可能是(arr1[n]+arr2[0])/2）
------
------
举个例子：
1 2 3 4
3 4 5 6
arr1[mid1]==2，arr2[mid2]==4,2<4,所以：
中位数必然存在于 3 4 3 4 中（即arr1[mid1+1:N]和arr2[0,mid2]）
也就是说，我们接下来只需要在arr1[mid1+1...n] 和 arr2[0...mid2] 中查找就行了。
要特别注意arr1（mid元素较小的那个数组）的范围是[mid1+1,N]而不是[mid1,N]！
当两个数组的长度为奇数时：
假定 arr1 = [1, 2,3,4，5]，arr2 = [3,4,5,6，7]。
则数组的⻓长度为 n = 5。
- mid1 = (n-1)/2 = 2。
- mid2 = (n - 1)/2 = 2。
这个时候如果 arr2[mid2] > arr1[mid1] 时，则和上面那个情况有点⼩小差别，这时候目标数只存在于 arr1[mid1...n] 和 arr2[0...mid2]中（mid1也包含在里面）。
（注意他们的差别，从arr1[mid1+1...n] => arr1[mid1...n]！！！至于为什么，自己去数一下元素个数就清楚了，比如说当长度是偶数时 1 2 3 4 和 3 4 5 6 ，那么arr1[mid+1,n]加上arr2[0,mid]的元素个数就是4个，刚好是总个数的一半，我们可以肯定中位数必然是在这两个区间里面；那么当长度是奇数时，如果你还是用mid+1的话，就用上面那个例子，arr1[mid+1,n]加上arr2[0,mid]的元素个数还是是4个,但总数是10个，这种情况我们就不能保证中位数在这arr1[mid+1,n]和arr2[0,mid]之中的，但如果是arr1[mid,n]加上arr2[0,mid]的话元素个数就是6个，虽然不可避免的要多判断一些个数，但是至少我们是能保证中位数在这两个区间里面。这就是原因。）
代码
特别注意：奇偶有可能是在不断变换着的，所以每次都要重新计算offset。
public int getUpMedian2(int[] arr1, int[] arr2) {
if (arr1 == null || arr2 == null) {
return -1;
}
int l1 = 0;
int r1 = arr1.length - 1;
int l2 = 0;
int r2 = arr2.length - 1;
int mid1 = 0;
int mid2 = 0;
int offset = 0;
while (l1 < r1) {
/*
这一句挺妙的，看似只判断了一种情况，其实包含了四种：
首先，r1可能始终不动（比如说始终为arr1.length-1），然后l1不断逼近它，也有
可能是l1始终不动（比如说始终为0），r1不断逼近0（当然，真实情况
可能是一会移动l1，一会移动r1，但不影响这个结论），
而不管哪一种，都可以用l1<r1来做约束；
然后，这两个数组，如果一个往左边缩，则另一个肯定会往右边缩，即
肯定会互相影响，肯定会导致l1往右边去或者r1往左边去，故曰，
这一句包含了四种情况
*/
mid1 = l1 + (r1 - l1) / 2;
mid2 = l2 + (r2 - l2) / 2;
offset = ((r1 - l1 + 1) & 1)^1; //奇数与1异或为0，偶数与1异或为1
if (arr1[mid1] < arr2[mid2]) {
l1 = mid1 + offset;
r2 = mid2;
} else if (arr1[mid1] > arr2[mid2]) {
r1 = mid1;
l2 = mid2 + offset;
} else {
return arr2[mid1];
}
}
return Math.min(arr1[l1], arr2[l2]);
}