LeetCode第四题：寻找两个有序数组的中位数
2019-09-29 本文已影响0人
躺在家里干活
题目
给定两个大小为 m 和 n 的有序数组 nums1 和 ums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为
说明
你可以假设 nums1 和 nums2 不会同时为空。
示例
===================
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
===================
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
===================
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思考过程
中位数：可以将一组数平分的数，就是一个数组中，小于这个数的数字和大于这个数的一样多
名词定义
left_count：表示小于中位数的数的数量
right_count：表示大于中位数的数的数量
left：左边的数
right：右边的
思路
- 我们需要在两个有序数组（A，B）中找到一个数，这个数可以将这这两个数组分割，分割的结果是
left_count = right_count - 问题转换：分别在
A，B中分别找到i，j个数，使得left_count = right_count或者left_count = right_count + 1；同时满足左边每一个数，小于右边每一个数
A.length = m
B.length = n
===============================================================
left | right
A[0],A[1]...A[i-1] | A[i],A[i+1],A[i+2]...A[m-1]
B[0],B[1]...B[j-1] | B[j],B[j+1],B[j+2]...B[n-1]
===============================================================
需要满足的条件：
1. left_count == right_count
2. A[i-1] <= B[j] && B[j-1] <= A[i]
- 问题转换：左边应该有几个数呢？A数组应该几个数在左边？B数组应该几个数在左边？
- 左边应该有几个数
因为两个数组的总长度是
当是偶数时，那么左边的数应该有
个
当个
由于当，所以左边的数应该有
结论：左边应该有个数，我们假设
A中有i个数在左边，B中有j个数在左边，此时
- 问题再次转换：如何找到这个
i呢？
什么方式找一个数最简单，当然是二分法了。。。。
可以参考算法中的分治法
实现
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
// 如果数组A长度位0
if (m == 0) {
if ((n & 1) == 1) {
return nums2[n / 2];
} else {
return (nums2[n / 2] + nums2[n / 2 - 1]) / 2.0;
}
}
// 如果数组B长度位0
if (n == 0) {
if ((m & 1) == 1) {
return nums1[m / 2];
} else {
return (nums1[m / 2] + nums1[m / 2 -1 ]) / 2.0;
}
}
// 如果数组B比数组A长，交换操作
if (n > m) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
int tempNum = m;
m = n;
n = tempNum;
}
// 左边需要多少个元素（数）
int targetLeftCount = (m + n + 1) / 2;
// 查询出数组A中有几个数在左边
int arrayANum = findNum(nums1, nums2, targetLeftCount, targetLeftCount, 0, m + 1);
double result;
// 下面是计算中位数的操作，主要就是小心数组越界访问
//奇数
if (((m + n) & 1) == 1) {
if (arrayANum == 0) {
result = nums2[n - 1];
} else if (targetLeftCount != arrayANum) {
result = Math.max(nums1[arrayANum - 1], nums2[targetLeftCount - arrayANum - 1]);
} else {
result = nums1[arrayANum - 1];
}
// 偶数
} else {
if (arrayANum == 0) {
result = (nums1[m - 1] + nums2[0]) / 2.0;
} else if (targetLeftCount != arrayANum) {
int j = targetLeftCount - arrayANum;
if (j == n) {
result = (Math.max(nums1[arrayANum - 1], nums2[j - 1]) + nums1[ arrayANum ]) / 2.0;
} else {
result = (Math.max(nums1[arrayANum - 1], nums2[j - 1]) + Math.min(nums2[j], nums1[arrayANum])) / 2.0;
}
} else {
if (arrayANum == m) {
return (nums1[m - 1] + nums2[0]) / 2.0;
} else {
result = (nums1[arrayANum - 1] + Math.min(nums2[0], nums1[arrayANum])) / 2.0;
}
}
}
return result;
}
// 类似二分查找
// 分解：查找中间数，判断当前数是不是满足条件
// 治理: 根据判断条件，一直使用上次循环的一半的复杂度（二分）进行递归操作。这里会递归执行（分解，治理，合并），每次递归复杂度都降低了一半
// 合并：此处没有合并,返回的值就是我们的求解
/**
* A数组需要有i个元素位于左边(A.length >= B.length),此时B数组有(target - i) 个元素位于左边
* @param nums1 有序数组A
* @param nums2 有序数组B
* @param i A数组中需要位于左边元素个数
* @param target 两个数组中，需要有几个元素位于左边
* @param minNum 最少有几个元素(本题中 minNum = 0)
* @param maxNum 最多能出几个元素(本题中 maxNum = A.length + 1) 注：这里虽然maxNum = A.length + 1,但是递归中 i 的计算方式是(i + maxNum) / 2，所以总会有 i < maxNum
* @return A数组中需要位于左边的元素个数
*/
private static int findNum(int[] nums1, int[] nums2, int i, int target, int minNum, int maxNum) {
// A数组有target个元素位于左边
if (i == target) {
// 如果此时A数组中第（i - 1）个元素，比B数组中的第一个元素小，说明找到了合适的（i）
if (nums1[i - 1] <= nums2[0]) {
// ===================================
// | 情况如下：
// | left | right
// | ____________________
// | 1,2,3,4,5 | 11 (数组A)
// | | 5,6,7 (数组B)
// | target = 5, i = 5
// ====================================
return i;
} else {
// 如果B中的第一个元素小于A[i-1],说明需要把B中的元素向左边移动,此时target不变,i就需要缩小，向左进行查找
// ===================================
// | 情况如下：
// | left | right
// | ____________________
// | 1,2,3,4,5 | 23,26 (数组A)
// | | 3,5 (数组B)
// | target = 5, i = 5
// ====================================
return findNum(nums1, nums2, (minNum + i) / 2, target, minNum, i);
}
} else {
// 计算此时B数组有(j)个元素位于左边
int j = target - i;
// 第一种情况：如果 j 大于 B数组的最大元素数，说明 i 太小了，需要向右进行查找
// ===================================
// | 情况如下：
// | left | right
// | ____________________
// | 1 | 2,3,5,6,23,26 (数组A)
// | | 3,5,6,7 (数组B)
// | target = 6, i = 1, j = 5
// | 此时 j > B.length = 4
// ====================================
// 第二种情况：如果A数组中的右边第一个数（A[i]），小于B数组左边最后一个数（B[j - 1]）,也说明 i 太小，需要向右查找
// ===================================
// | 情况如下：
// | left | right
// | ____________________
// | 1,2,3 | 4,23,26 (数组A)
// | 4,5,6 | 6,8,12 (数组B)
// | target = 6 ((6 + 6 + 1)/2), i = 3, j = 3
// | 此时 A[3] = 3.5, B[2] = 6,B中的元素需要继续往右边转移 -> 减小j -> 增加i -> 继续向右搜索
// ====================================
if (nums2.length < j || nums1[i] < nums2[j - 1]) {
return findNum(nums1, nums2, (i + maxNum) / 2, target, i, maxNum);
} else if (nums2.length > j && nums1[i - 1] > nums2[j]) {
// 第一个条件：B.length > j
// 此时需要向左搜索i -> i变小 -> j变大 所以要判断B是否还有变大的空间
// ===================================
// | 情况如下：
// | left | right
// | ____________________
// | 4,5,6 | 10,23,26 (数组A)
// | 1,2,3 | 4,8,12 (数组B)
// | target = 6 ((6 + 6 + 1)/2), i = 3, j = 3
// | 此时 A[i - 1] = 6 > B[j] = 4，说明还需要向左进行搜索，让B数组向左移动
// ====================================
return findNum(nums1, nums2, (minNum + i) / 2, target, minNum, i);
} else {
// 上面两个分支，处理了所有需要再次查找 i 的情况，如果程序执行到这里，那么 i 就是我们需要找到的值
// 需要说明的情况
// 1. i = 0 的情况,由于我们是从中间进行二分查找，并且数字都是连续的，所有 i = 0 肯定是向左搜索的最后一种情况，此时A中的元素均大于B中的元素
// ===================================
// | 情况如下：
// | left | right
// | ____________________
// | | 4,23,26 (数组A)
// | 1,2,3 | (数组B)
// | target = 3, i = 0, j = 3
// =========================================
// 2. B.length = j 的情况
// ===================================
// | 情况如下：
// | left | right
// | ____________________
// | 4,5 | 23,26 (数组A)
// | 3 | (数组B)
// | target = 3, i = 2, j = 1
// =========================================
return i;
}
}
}
}
执行结果：
执行用时 :3 ms, 在所有 Java 提交中击败了99.81%的用户
内存消耗 :47.4 MB, 在所有 Java 提交中击败了92.98%的用户
其他语言解法
1.JS
var findMedianSortedArrays = function(nums1, nums2) {
if (nums1.length > nums2.length) [nums1, nums2] = [nums2, nums1];
const length1 = nums1.length;
const length2 = nums2.length;
let min = 0;
let max = length1;
let half = Math.floor((length1 + length2 + 1) / 2);
while (max >= min) {
const i = Math.floor((max + min) / 2);
const j = half - i;
if (i > min && nums1[i - 1] > nums2[j]) {
max = i - 1;
} else if (i < max && nums1[i] < nums2[j - 1]) {
min = i + 1;
} else {
let left,right;
if (i === 0) left = nums2[j - 1];
else if (j === 0) left = nums1[i - 1];
else left = Math.max(nums1[i - 1], nums2[j - 1]);
if (i === length1) right = nums2[j];
else if (j === length2) right = nums1[i];
else right = Math.min(nums1[i], nums2[j]);
return (length1 + length2) % 2 ? left : (left + right) / 2;
}
}
return 0;
};
