寻找两个正序数组的中位数
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
方法一：先合并，再取中位数
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
int[] temp = new int[len];
int i = 0, j = 0, k = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) {
temp[k++] = nums1[i++];
} else {
temp[k++] = nums2[j++];
}
}
while (i < nums1.length) {
temp[k++] = nums1[i++];
}
while (j < nums2.length) {
temp[k++] = nums2[j++];
}
if (len % 2 == 0) {
return (temp[len / 2] + temp[len / 2 - 1]) / 2.0;
} else {
return temp[len / 2];
}
}
方法二：找中位数位置
为统一处理奇数和偶数情况，用left和right两个变量保存当前循环的值，每次用left替换right，表示上一个位置的值
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
int i = 0, j = 0;
int left = 0, right = 0;
while (i + j <= len / 2) {
left = right;
if (i < nums1.length && (j >= nums2.length || nums1[i] < nums2[j])) {
right = nums1[i];
i++;
} else {
right = nums2[j];
j++;
}
}
if (len % 2 == 0) {
return (left + right) / 2.0;
} else {
return right;
}
}
方法三：求两个数组中第k小的数
求两个数组中第k小的数：
由于4 < 12 ，抛弃掉A组的前4个元素，指针向后移动
总之就是每轮抛弃掉小于第k小元素的前k/2个
对抛弃掉的元素一定不是第k小的证明：
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len = nums1.length + nums2.length;
if (len % 2 == 0) {
return (findKNums(nums1, nums2, len / 2) + findKNums(nums1, nums2, len / 2 + 1)) / 2.0;
} else {
return findKNums(nums1, nums2, len / 2 + 1);
}
}
public int findKNums(int[] nums1, int[] nums2, int k) {
int i = 0, j = 0;
while (true) {
if (i >= nums1.length) { //一个数组所有元素都删完了，第k小的数一定在另一个数组中
return nums2[j + k - 1];
}
if (j >= nums2.length) {
return nums1[i + k - 1];
}
if (k == 1) {
return Math.min(nums1[i], nums2[j]);
}
int half = k / 2;
int index1 = i + half - 1 >= nums1.length ? nums1.length - 1 : i + half - 1; //考虑数组剩余元素不够half个，最多只能取到末尾
int index2 = j + half - 1 >= nums2.length ? nums2.length - 1 : j + half - 1;
if (nums1[index1] < nums2[index2]) {
k -= index1 - i + 1;
i = index1 + 1;
} else {
k -= index2 - j + 1;
j = index2 + 1;
}
}
}
时间复杂度：O(log(m+n))
方法四：划分数组
中位数将数组划分为两部分，不妨将中位数划分到左部分
如果是偶数，则为分割线左边最大的元素与右边最小元素的平均值
如果是奇数，则为分割线左边最大的元素
假设数组1长度为m，数组2长度为n
如果是偶数，划分在左边的元素个数(m+n)/2，由于除是向下取整，所以可以统一(m+n+1)/2
如果是奇数，划分在左边的元素个数(m+n+1)/2
左边的所有元素小于等于右边的所有元素：
- 第一个数组左边最后一个元素小于等于第二个数组右边第一个元素
- 不满足条件说明第一个数组的边界线应该向左移
- 第二个数组左边最后一个元素小于等于第一个数组右边第一个元素
- 不满足条件说明第一个数组的边界线应该向右移
特殊情况：
分割线的定义：分割线在数组的下标i=分割线左边的元素个数
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int len = nums1.length + nums2.length;
int totalLeft = (len + 1) / 2;
int left = 0;
int right = nums1.length;
while (left < right) {
int i = (left + right + 1) / 2; //加1是为了防止只有一个元素时left = i进入死循环
int j = totalLeft - i;
if (nums1[i - 1] > nums2[j]) {
right = i - 1;
} else {
left = i;
}
}
int i = left;
int j = totalLeft - i;
int num1Left = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
int num1Right = i == nums1.length ? Integer.MAX_VALUE : nums1[i];
int num2Left = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
int num2Right = j == nums2.length ? Integer.MAX_VALUE : nums2[j];
if (len % 2 == 0) {
return (Math.max(num1Left, num2Left) + Math.min(num1Right, num2Right)) / 2.0;
} else {
return Math.max(num1Left, num2Left);
}
}
时间复杂度：O(logmin(m,n)))
