刷题打卡：在两个长度相等的排序数组中找到上中位数
【题目】
给定两个有序数组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.
【难度】
中
【解答】
这道题可以采用递归来解决，注意，这道题数组是有序的，所以它有如下特点：
(1)、当 两个数组的长度为偶数时：
我来举个例子说明他拥有的特点吧。我们假定 arr1 = [1, 2,3,4]，arr2 = [3,4,5,6]。则数组的长度为 n = 4。
分别选出这两个数组的上中位数的下标，即
mid1 = (n-1)/2 = 1。
mid2 = (n - 1)/2 = 1。
假如 arr2[mid2] > arr2[mid1]，那么我们要找的目标数是一定存在于 arr1[mid1+1…n] 和 arr2[0…mid2]中。而不可能存在于 arr1[0…mid1] 和 arr2[mid2+1…n] 之中。
也就是说，我们接下来只需要在arr1[mid1+1…n] 和 arr2[0…mid2] 中查找就行了。
(2)、当两个数组的长度为奇数时：
假定 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]中。注意他们的差别，从arr1[mid1+1…n] => arr1[mid1…n]。
理解了这个原理，配合上代码会更好理解，代码如下：
1 public static int getUpMedian(int[] arr1, int[] arr2) {
2 if(arr1 == null || arr2 == null )
3 return -1;
4 // 开始寻找
5 return find(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1);
6 }
7
8 public static int find(int[] arr1, int l1, int r1, int[] arr2, int l2, int r2) {
9 int mid1 = l1 + (r1 - l1) / 2;
10 int mid2 = l2 + (r2 - l2) / 2;
11 // 表示数组只剩下一个数，把两个数组中较小的数返回去
12 if (l1 >= r1) {
13 return Math.min(arr1[l1], arr2[l2]);
14 }
15 // 元素个数为奇数，则offset为0，为偶数则 offset 为 1
16 int offset = ((r1 - l1 + 1) & 1) ^ 1;// 用位运算比较快
17 if (arr1[mid1] < arr2[mid2]) {
18 return find(arr1, mid1+offset, r1, arr2, l2, mid2);
19 } else if (arr1[mid1] > arr2[mid2]) {
20 return find(arr1, l1, mid1, arr2, mid2 + offset, r2);
21 } else {
22 return arr1[mid1];// 返回 arr2[mid2]也可以。
23 }
24 }也可以用迭代来做，反而更加简单，迭代版本如下：
1 // 迭代版本
2 public int getUpMedian2(int[] arr1, int[] arr2) {
3 if (arr1 == null || arr2 == null) {
4 return -1;
5 }
6 int l1 = 0;
7 int r1 = arr1.length - 1;
8 int l2 = 0;
9 int r2 = arr2.length - 1;
10 int mid1 = 0;
11 int mid2 = 0;
12 int offset = 0;
13 while (l1 < r1) {
14 mid1 = l1 + (r1 - l1) / 2;
15 mid2 = l2 + (r2 - l2) / 2;
16 offset = ((r1 - l1 + 1) & 1)^1;
17 if (arr1[mid1] < arr2[mid2]) {
18 l1 = mid1 + offset;
19 r2 = mid2;
20 } else if (arr1[mid1] > arr2[mid2]) {
21 r1 = mid1;
22 l2 = mid2 + offset;
23 } else {
24 return arr2[mid1];
25 }
26 }
27 return Math.min(arr1[l1], arr2[l2]);
28 }像这种题理解虽然不难，但要准确写出来还是挺不容易的，有很多临界点需要考虑，后面，我会再给出两个类似的题，算是这道题的进阶版。
往期
腾讯云开发者
