题目描述
解题思路
此题目直接遍历两个列表，时间复杂度为O(n)；使用二分法去比较两个递增列表的中位数，缩小两个数组中位数范围，时间复杂度O(logn)，这里我们的算法实现使用二分法。
通过举例子来说明解题算法：
在循环过程中，每时每刻都保持两个比较列表的长度是相等的。
1.当两个列表 [low1,high1] 和 [low2,high2] 的中位数相等时：
[1,3,4,5]和[2,3,5,6]=[1,2,3,3,4,5,5,6]
[1,4,5,6,7]和[2,3,5,7,8]=[1,2,3,4,5,5,6,7,7,8]
可以看到，无论（high1-low1+1）是奇数还是偶数，当arr[mid]相等时，上中位数就是arr[mid]
2.当两个列表 [low1,high1] 和 [low2,high2] 的中位数arr1[mid1]<arr2[mid2]时：
当（high1-low1+1）是奇数时：[1,2,4,8,9] 和 [2,3,5,7,9] low1=mid1；high2 = mid2;
当（high1-low1+1）是偶数时：[1,2,4,8] 和 [2,3,4,7] low1=mid1+1；high2 = mid2;
缩小范围到黄色加粗内。
3.当两个列表 [low1,high1] 和 [low2,high2] 的中位数arr1[mid1]>arr2[mid2]时：
当（high1-low1+1）是奇数时：[1,5,7,8,9] 和 [2,3,5,7,9] low2=mid2；high1 = mid1;
当（high1-low1+1）是偶数时：[1,5,7,8] 和 [2,3,4,7] low2=mid2+1；high1 = mid1;
缩小范围到黄色加粗内。
4.最后返回arr1[low1]和arr2[low2]中的较小者。
代码实现
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* find median in two sorted array
* @param arr1 int整型一维数组 the array1
* @param arr2 int整型一维数组 the array2
* @return int整型
*/
//这里直接遍历两个列表，时间复杂度为O(n)
//使用二分法去比较两个递增列表的中位数，缩小两个数组中位数范围，时间复杂度O(logn)
public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
// 这里使用二分法
int res = 0;
int low1 = 0, high1 = arr1.length - 1;
int low2 = 0, high2 = arr2.length - 1;
while (low1 < high1) {
int mid1 = (low1 + high1) / 2;
int mid2 = (low2 + high2) / 2;
if (arr1[mid1] == arr2[mid2]) {
//这个不管是奇数还是偶数都成立：
//[1,3,4,5]和[2,3,5,6]=[1,2,3,3,4,5,5,6]
//[1,4,5,6,7]和[2,3,5,7,8]=[1,2,3,4,5,5,6,7,7,8]
low1 = mid1;
low2 = mid2;
break;
} else if (arr1[mid1] < arr2[mid2]) {
if ((high1 - low1 + 1) % 2 == 1) { //如果high1-low1+1为奇数
//比如[1,2,4,8,9]和[2,3,5,7,9]
low1 = mid1;
high2 = mid2;
} else { //如果high1-low1+1为偶数
//比如[1,2,4,8]和[2,3,4,7]
low1 = mid1 + 1;
high2 = mid2;
}
} else {
if ((high1 - low1 + 1) % 2 == 1) { //如果high1-low1+1为奇数
//比如[1,5,7,8,9]和[2,3,5,7,9]
low2 = mid2;
high1 = mid1;
} else { //如果high1-low1+1为偶数
//比如[1,5,7,8]和[2,3,4,7]
high1 = mid1;
low2 = mid2 + 1;
}
}
}
res = arr1[low1] < arr2[low2] ? arr1[low1] : arr2[low2];
return res;
}
}
