4. Median of Two Sorted Arrays

Posted on | In |

LeetCode 4. Median of Two Sorted Arrays

按照题目描述，我们要求出两个已排序数组的中位数。

先上代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length, n = nums2.length;
    if (m > n) {
        int temp = m;
        m = n;
        n = temp;
        int[] tempList = nums1;
        nums1 = nums2;
        nums2 = tempList;
    }
    int left = 0, right = m - 1;
    int halfLen = (m + n + 1) / 2;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int j = halfLen - mid;
        if (mid > 0 && nums1[mid - 1] > nums2[j]) {
            right = mid - 1;
        } else if (mid < m && nums1[mid] < nums2[j - 1]) {
            left = mid + 1;
        } else {
            left = mid;
            break;
        }
    }
    int midLeft1 = left >= 1 ? nums1[left - 1] : nums2[halfLen - left - 1];
    int midLeft2 = halfLen - left >= 1 ? nums2[halfLen - left - 1] : nums1[left - 1];
    int midLeft = midLeft1 > midLeft2 ? midLeft1 : midLeft2;
    int midRight;
    if ((m + n) % 2 == 1) {
        midRight = midLeft;
    } else {
        int midRight1 = left < m ? nums1[left] : nums2[halfLen - left];
        int midRight2 = halfLen - left < n ? nums2[halfLen - left] : nums1[left];
        midRight = midRight1 < midRight2 ? midRight1 : midRight2;
    }
    return ((double) midLeft + (double) midRight) / 2.0;
}

考虑这个题目。一种直观的解法是先计算出两个数组的总长度，然后根据数组的长度同时遍历两个数组，直到找到目标元素，并计算出中位数。但是这种方法的时间复杂度是O(n)。考虑更快的算法，因为两个数组已经经过排序，所以二分查找可能会有更好的性能。参考LeetCode的答案。

这种解法的基本想法是对其中一个数组进行二分搜索，由于要寻找中位数，所以两个数组的下标i和j，两个数组的长度m和n，满足i + j == (m + n + 1) / 2。所以移动i相应的j也会自动移动。而我们搜索的条件是，找到合理的i和j，使得nums1[i - 1] < nums2[j]和nums2[j - 1] < nums1[i]同时成立。

代码可以分成三部分。

  • 第一部分，判断并且交换两个数组，使得nums1的长度比nums2小。这样做是为了计算出的nums2的下标不会为负。

  • 第二部分，对数组nums1进行二分搜索，找出满足条件的下标值，在代码中是left，使得两个数组满足上述条件。

  • 第三部分，根据找到的两个数组的下标，判断越界情况，并且根据数组长度的奇偶性计算出最后的中位数值。

这道题目的思路简单，关键在于合理处理下标，判断越界情况，得出正确结果。