题目
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
解析：
思路：二分查找
二分查找常用于有序的查找，所以这道题也能用。但稍有不同的是需要对两组有序数组找其中位数，相当于两个数组合并排序后的中位数，且题目也要求了算法复杂度为log(m+n)，这就要求我们直接对已有的两组数据进行操作。
对于给定的两个有序数组a,b，长度分别为 m和n，我们可以理解为要找第几小的数字。比如m+n为9，则我们需要找第5小的数字。设k=5，i=k/2，每次取两个数字的第i个数字进行比较，谁的第i个数字小，则谁的前i个数字都舍弃掉（可以理解为所以变成从i 开始）。接着，开始第二轮，k=k-i, i = k/2（这一步很关键，其实i就是每次二分查找的步长，按照每次比较的结果落在对应的数字上，）继续比较a(i)和b(i)，然后谁小，前i个数字都舍弃。以此往复，直到i为0。实际上，每次比较都会舍弃k/2个数字，其实就是二分查找。只是这个累计的过程分布在了两个数组上。
当然以上是正常情况，还有一些特殊情况，由于某个数组过短，导致以上假设不成立，那就采取特殊处理，用长的减去短的数组，然后直接求中位数即可。
实现
java版本，感觉实现的有点啰嗦，没有良好的抽象，后续需要再精简精简：
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int nums1L = nums1.length;
int nums2L = nums2.length;
// 其中一个为空的情况
if (nums1L == 0 && nums2L != 0) {
return sortedArrayMid(nums2, nums2L);
} else if (nums1L != 0 && nums2L == 0) {
return sortedArrayMid(nums1, nums1L);
}
// 两个都不为空的情况, 但是连续
if (nums1[nums1L -1] <= nums2[0]) {
return sortedArrayMid(nums1, nums2);
} else if (nums2[nums2L - 1] <= nums1[0]) {
return sortedArrayMid(nums2, nums1);
}
// 常规情况
int total = nums1L + nums2L; // 总数
int half = total / 2; // 一半
int a = 0, b = 0; // 索引记录
boolean odd = total % 2 == 1; // 总和是否为奇数
int k = half + (odd ? 1 : 0); // 要寻找的目标索引
int i; // 迭代索引增量 总是为k的一半, 可以理解为k的二分查找
while ((i = k / 2) != 0) {
int ia = a + i - 1;
int ib = b + i - 1;
if (ia > nums1L - 1) {
ia = nums1L - 1;
}
if (ib > nums2L - 1) {
ib = nums2L - 1;
}
if (nums1[ia] < nums2[ib]) {
if (ia + 1 == nums1L) {
a = ia;
break;
} else {
a = ia + 1;
}
} else if (nums1[ia] > nums2[ib]) {
if (ib + 1 == nums2L) {
b = ib;
break;
} else {
b = ib + 1;
}
} else if (a >= b) {
if (ia + 1 == nums1L) {
a = ia;
break;
} else {
a = ia + 1;
}
} else {
if (ib + 1 == nums2L) {
b = ib;
break;
} else {
b = ib + 1;
}
}
k = k - i;
}
int numa = nums1[a];
int numb = nums2[b];
// k != 1 说明迭代没有走完，提前截断了
if (k != 1) {
if (odd) {
if (a == nums1L - 1) {
return nums2[half - nums1L];
} else {
return nums1[half - nums2L];
}
}
if (a == nums1L - 1) {
int x = nums2[half - nums1L - 1];
int y = nums2[half - nums1L];
if (numa <= x || numa >= y) {
return ((double) x + y) / 2;
} else {
return (double)(numa + y) / 2;
}
} else {
int x = nums1[half - nums2L - 1];
int y = nums1[half - nums2L];
if (numb <= x || numb >= y) {
return ((double) x + y) / 2;
} else {
return (double)(numb + y) / 2;
}
}
} else if (odd) {
return Math.min(numa, numb);
} else {
boolean aLess = numa < numb;
int mid = aLess ? numa : numb;
int other;
if (aLess) {
other = a + 1 >= nums1L ? numb : Math.min(nums1[a + 1], numb);
} else {
other = b + 1 >= nums2L ? numa : Math.min(numa, nums2[1 + b]);
}
return ((double) other + mid) / 2;
}
}
static double avg(int a, int b) {
return ((double) a + b) / 2;
}
static double sortedArrayMid(int[] nums1, int nums1L) {
if (nums1L % 2 == 0) {
int mid = nums1L / 2;
return ((double) (nums1[mid - 1] + nums1[mid])) / 2;
} else {
return nums1[nums1L / 2];
}
}
static double sortedArrayMid(int[] nums1, int[] nums2) {
int nums1L = nums1.length;
int nums2L = nums2.length;
int total = nums1L + nums2L;
int half = total / 2;
if (total % 2 == 1) {
if (nums1L <= half) {
return nums2[half - nums1L];
} else {
return nums1[half];
}
}
if (nums1L > half) {
return avg(nums1[half], nums1[half - 1]);
} else if (nums1L < half) {
int start = half - nums1L;
return avg(nums2[start], nums2[start - 1]);
} else {
return avg(nums1[nums1L - 1], nums2[0]);
}
}
}
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
网友评论