[关闭]
@Yano 2018-11-24T07:10:26.000000Z 字数 1791 阅读 1181

LeetCode 004 Median of Two Sorted Arrays 详细分析

LeetCode


题目链接:https://leetcode.com/problems/median-of-two-sorted-arrays/

我一直会卡在这道题上,在网上看了半个小时的博客,愣是没看懂。后来看到 YouTube 上有一个印度大哥的讲解,豁然开朗。

印度大哥的视频地址:Binary Search : Median of two sorted arrays of different sizes.

题目描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

题目分析

其实这道题我卡就卡在,一直没有想清楚应该如何划分两个数组。直接看LeetCode论坛上的答案,也一直没有搞懂。本题只是想求中位数,并不用管其他的数字。

那么核心就在于,如何划分两个数组,使得两个数组组合起来后,成为一个在中位数附近相对有序的数组即可。

具体实例分析

算法分析

定义两个变量 partitionX、 partitionY,分别分割X数组和Y数组,记为X1, X2, Y1, Y2。使得

len(X1) + len(Y1) == len(X2) + len(Y2)
或
len(X1) + len(Y1) == len(X2) + len(Y2) + 1

并且使得 max(X1) < min(Y2), max(Y1) < min(X2),这样数组就被完整地分成了两部分。

如果两个数组长度的和是奇数,那么必然是 max(X1, Y1)了;
如果两个数组长度的和是偶数,那么是 (max(X1, Y1) + min(X2, Y2)) / 2。

代码实现

  1. public double findMedianSortedArrays(int[] nums1, int[] nums2) {
  2. if (nums1.length > nums2.length) {
  3. return findMedianSortedArrays(nums2, nums1);
  4. }
  5. int x = nums1.length, y = nums2.length;
  6. int low = 0, high = x;
  7. while (low <= high) {
  8. int partitionX = (low + high) / 2;
  9. int partitionY = (x + y + 1) / 2 - partitionX;
  10. int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
  11. int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
  12. int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
  13. int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
  14. if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
  15. if ((x + y) % 2 == 0) {
  16. return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
  17. } else {
  18. return Math.max(maxLeftX, maxLeftY);
  19. }
  20. } else if (minRightX < maxLeftY) {
  21. low = partitionX + 1;
  22. } else {
  23. high = partitionX - 1;
  24. }
  25. }
  26. throw new RuntimeException();
  27. }

总结

这道题如果能把图画出来,理解起来就很容易。但是这道题在LeetCode中的难度是hard,因为编写代码并不容易,有很多边界条件:
1. 数组长度的奇偶
2. 移动过程中,某个数组被切割后可能为空

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注