4. Median of Two Sorted Arrays
程序员文章站
2022-03-03 09:04:41
...
Description
https://leetcode.com/problems/median-of-two-sorted-arrays/
题目大意:
给定两个有序数组nums1和nums2,长度分别为m和n,要求在O(log(m+n))时间复杂度内找出两个有序数组的中位数。
Solving Ideas
https://www.youtube.com/watch?v=LPFhl65R7ww
基本思路:
利用二分查找,寻找较短数组(假设为nums1)的分割点,根据这个分割点,确定nums2的分割点,使其满足 maxLeftX<=minRightY && maxLeftY<=minRightX 。
maxLeftX表示nums1分割点左边的元素,minRightX表示nums1分割点右边的元素,同理可知maxLeftY表示nums2分割点左边的元素,minRightY表示nums2分割点右边的元素。
确定nums2的分割点时,需要满足:
leftPartX + leftPartY = rightPartX + rightPartY
或者
leftPartX + leftPartY = rightPartX + rightPartY + 1
leftPartX: nums1分割后左子数组的长度
RightPartX: nums1分割后右子数组的长度
leftPartY: nums2分割后左子数组的长度
RightPartY: nums2分割后右子数组的长度
找到满足上述两个条件的分割点后,两个有序数组的中位数就可以由两个分割点左右两边的元素最终确定了。
因为是折半查找较短数组的分割点,故时间复杂度为O(log(min(m, n)))
Solution
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int lenX = nums1.length, lenY = nums2.length;
int left = 0, right = lenX;
while (left <= right) {
int partitionX = (left + right) / 2;
int partitionY = (lenX + lenY + 1) / 2 - partitionX;
int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
int minRightX = (partitionX == lenX) ? Integer.MAX_VALUE : nums1[partitionX];
int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
int minRightY = (partitionY == lenY) ? Integer.MAX_VALUE : nums2[partitionY];
if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
if ((lenX + lenY) % 2 == 0) {
return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
}else {
return Math.max(maxLeftX, maxLeftY);
}
} else if (maxLeftY > minRightX) left = partitionX + 1;
else right = partitionX - 1;
}
return -1.0;
}
}
推荐阅读
-
【LeetCode】4. Median of Two Sorted Arrays
-
1.Merge Two Sorted Arrays. py/合并排序有序数列
-
LeetCode 4. 两个排序数组的中位数 Median of Two Sorted Arrays
-
算法练习(3):Median of Two Sorted Arrays
-
LeetCode算法系列:4、Median of Two Sorted Arrays
-
4. Median of Two Sorted Arrays
-
4. Median of Two Sorted Arrays
-
【leetcode】4. Median of Two Sorted Arrays
-
【leetcode阿里题库】4. Median of Two Sorted Arrays
-
Median of Two Sorted Arrays(C++)