【LeetCode】004：寻找两个正序数组的中位数-白红宇

【LeetCode】004：寻找两个正序数组的中位数

阅读量：2054 次

发布时间：2019-04-28

本文共 12133 字，大约阅读时间需要 40 分钟。

记录一下自己的练习。

题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

输入：nums1 = [], nums2 = [1]
输出：1.00000

方法

方法一：合并数组

解题思路

只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。假设两个数组的长度分别为 $m$ , $n$ ，如果 $m + n$ 为奇数时，中位数是两个有序数组中的下标为 $(m + n) / 2$ 的元素；当 $m + n$ 为偶数时，中位数是两个有序数组中的下标为 $(m + n) / 2 - 1$ 的元素和下标为 $(m + n) / 2$ 的元素的平均值。

维护两个指针，初始时分别指向两个数组的下标 $0$ 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。

如果一个数组已经遍历完，仍没有找到中位数，则直接计算跳跃的步数来找中位数。

在这里插入图片描述

代码

class Solution {
       public double findMedianSortedArrays(int[] nums1, int[] nums2) {
           int m = nums1.length;        int n = nums2.length;        int len = m + n;        int left = 0;        int right = 0;        //合并之后的下标        int index = -1;        int i = 0, j = 0;        while(i < m && j < n){
               index++;            left = right;            if(nums1[i] < nums2[j]){
                   right = nums1[i++];            }else {
                   right = nums2[j++];            }            // 找到中位数，直接返回结果            if(index == len / 2){
                   return len % 2 == 0 ? (left + right) / 2.0 : right;            }        }        // 遍历完其中一个数组，还没找到中位数，直接计算下标差        // 由于 下标 都进行了 加1 操作，所以计算步数时，需要减1        int steps = len / 2 - index - 1;        // 需要找到 len / 2 - 1        if(i
   
     0 ? nums1[i + steps - 1] : right;            right = nums1[i + steps];        } else {
               left = steps > 0 ? nums2[j + steps - 1]: right;            right = nums2[j + steps];        }        return len % 2 == 0 ? (left + right) / 2.0 : right;    }}

复杂度分析

时间复杂度： $O (m + n)$ ，其中其中 $m$ 和 $n$ 分别是数组 $n u m s 1$ 、 $n u m s 2$ 的长度。
空间复杂度： $O (1)$ 。

方法二：二分法

解题思路

根据中位数的定义，当 $m + n$ 是奇数时，中位数是两个有序数组中的第 $(m + n) / 2 + 1$ 个元素，当 $m + n$ 是偶数时，中位数是两个有序数组中的第 $(m + n) / 2$ 个元素和第 $(m + n) / 2 + 1$ 个元素的平均值。因此，这道题可以转化成寻找两个有序数组中的第 $k$ 小的数，其中 $k$ 为 $(m + n) / 2$ 或 $(m + n) / 2 + 1$ 。

假设两个有序数组分别是 $n u m s 1$ 、 $n u m s 2$ 。要找到第 $k$ 个元素，我们可以比较 $n u m s 1 [k / 2 - 1]$ 和 $n u m s 2 [k / 2 - 1]$ 。
在 $n u m s 1 [k / 2 - 1]$ 前面的元素个数有 $k / 2 - 1$ 个，在 $n u m s 2 [k / 2 - 1]$ 前面的元素个数有 $k / 2 - 1$ 个，对于 $n u m s 1 [k / 2 - 1]$ 和 $n u m s 2 [k / 2 - 1]$ 中较小者，最多有 $k / 2 - 1 + k / 2 - 1 = k - 2$ 个元素比它小,即不可能是第 $k$ 小的数。

有以下三种情况需要特殊处理：

如果下标为 $k / 2 - 1$ 越界，那么选取对应数组中的最后一个元素，同时根据排除数的个数减少 $k$ 的值。

如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 $k$ 小的元素。

如果 $k = 1$ ，我们只要返回两个数组首元素的最小值即可。

示例

假设两个有序数组如下：

$s u m s 1$ : 1 3 4 9
$s u m s 2$ : 1 2 3 4 5 6 7 8 9

两个有序数组的长度分别是 $m = 4$ 和 $n = 9$ ，长度之和是 $m + n = 13$ ，中位数是两个有序数组中的第 $k = (m + n) / 2 + 1 = 7$ 个元素，因此需要找到第 7 个元素。

比较两个有序数组中下标为 $k / 2 - 1 = 2$ 的数，即 $s u m s 1 [2]$ 和 $s u m s 2 [2]$ ：

在这里插入图片描述

由于 $s u m s 1 [2] > s u m s 2 [2]$ ，因此排除 $s u m s 2 [0]$ 、 $s u m s 2 [1]$ 、 $s u m s 2 [2]$ ，即数组 $s u m s 2$ 的下标偏移（offset）变为 $3$ ，数组 $s u m s 1$ 的下标偏移（offset）仍为 $0$ 。

排除数的个数： $k / 2 = 3$ ; 更新 $k$ 的值： $k = k - k / 2 = 7 - 3 = 4$ 。

比较两个有序数组中下标为 $o f f s e t + k / 2 - 1$ 的数，即 $s u m s 1 [1]$ 和 $s u m s 2 [4]$ ：

由于 $s u m s 1 [1] < s u m s 2 [4]$ ，因此排除 $s u m s 1 [0]$ 、 $s u m s 1 [1]$ ，即数组 $s u m s 1$ 的下标偏移（offset）变为 $2$ ，数组 $s u m s 2$ 的下标偏移（offset）仍为 $3$ 。

排除数的个数： $3 + k / 2 = 5$ ; 更新 $k$ 的值： $k = k - k / 2 = 4 - 2 = 2$ 。

比较两个有序数组中下标为 $k / 2 - 1 = 0$ 的数，即 $s u m s 1 [2]$ 和 $s u m s 2 [2]$ ：

由于 $s u m s 1 [2] = s u m s 2 [3]$ ，因此排除 $s u m s 1 [2]$ ，即数组 $s u m s 1$ 的下标偏移（offset）变为 $3$ ，数组 $s u m s 2$ 的下标偏移（offset）仍为 $3$ 。

排除数的个数： $5 + k / 2 = 6$ ; 更新 $k$ 的值： $k = k - k / 2 = 2 - 1 = 1$ 。

由于 $k$ 的值变成 $1$ ，因此比较两个有序数组中的未排除下标范围内的第一个数，其中较小的数即为第 $k$ 个数:

由于 $s u m s 1 [3] > s u m s 2 [3]$ ，因此第 $k$ 个数是 $s u m s 2 [3]$ 。

代码

public double findMedianSortedArrays_2(int[] nums1, int[] nums2) {
           /**         * 当 m+n 是 奇数 时，中位数是两个有序数组中的第 (m+n)/2+1 个元素         * 当 m+n 是 偶数 时，中位数是两个有序数组中的第 (m+n)/2 个元素和第 (m+n)/2+1 个元素的平均值         */        int len = nums1.length + nums2.length;        double median;        if (len % 2 == 1) {
               median = getKthElement(nums1, nums2, len / 2 + 1);        } else {
               median = (getKthElement(nums1, nums2, len / 2) + getKthElement(nums1, nums2, len / 2 + 1)) / 2.0;        }        return median;    }     	/**     * 找到第 k (k>1) 小的元素     * 循环取下标为 k/2-1 的两个元素进行比较,即 sums1[k/2-1]和 sums2[k/2-1]     * 如果 sums1[k/2-1] <= sums2[k/2-1]) , 则 sums1 的 offset 变成 k/2, 即 sums1[0] 到 sums1[k/2-1] 都被剔除掉；     * 如果 sums1[k/2-1] > sums2[k/2-1]) , 则 sums2 的 offset 变成 k/2, 即 sums2[0] 到 sums2[k/2-1] 都被剔除掉。     * 更新 k = k - k/2。     * 如果 下标 k/2-1 越界， 则 取 数组中最后一个， 更新 k 值 时，减去实际减少的值；     * 如果  k = 1, 返回较小值， 即为 第 k 小的元素。     *     */    public int getKthElement(int[] nums1, int[] nums2, int k) {
           int length1 = nums1.length;        int length2 = nums2.length;        int index1 = 0, index2 = 0;        while (true) {
               // 边界情况            if (index1 == length1) {
                   return nums2[index2 + k - 1];            }            if (index2 == length2) {
                   return nums1[index1 + k - 1];            }            if (k == 1) {
                   return Math.min(nums1[index1], nums2[index2]);            }            // 正常情况            int half = k / 2;                        int newIndex1 = Math.min(index1 + half, length1) - 1;                        int newIndex2 = Math.min(index2 + half, length2) - 1;                     if (nums1[newIndex1] <= nums2[newIndex2]) {
                   k = k - (newIndex1 - index1 + 1);                index1 = newIndex1 + 1;            } else {
                   k = k - (newIndex2 - index2 + 1);                index2 = newIndex2 + 1;            }        }    }

复杂度分析

时间复杂度： $O (l o g (m + n))$ ，其中 $m$ 和 $n$ 分别是数组 $n u m s 1$ 和 $n u m s 2$ 的长度。
空间复杂度： $O (1)$ 。

方法三：划分数组【官方答案】

解题思路

首先，在任意位置 $i$ 将 $s u m s 1$ 划分成两个部分：

left_sums1 | right_sums1
sums1[0], sums1[1], … , sums1[i-1] | sums1[i], sums1[i+1], … , sums1[m-1]

采用同样的方式，在任意位置 $j$ 将 $s u m s 2$ 划分成两个部分：

left_sums2 | right_sums2
sums2[0], sums2[1], … , sums2[j-1] | sums2[j], sums2[j+1], … , sums2[n-1]

将 left_sums1 和 left_sums2$ 放入一个集合，并将 right_sums1 和 right_sums2 放入另一个集合。再把这两个新的集合分别命名为 left_part 和 right_part：

left_part | right_part
sums1[0], sums1[1], … , sums1[i-1] | sums1[i], sums1[i+1], … , sums1[m-1]
sums2[0], sums2[1], … , sums2[j-1] | sums2[j], sums2[j+1], … , sums2[n-1]

当 $s u m s 1$ 和 $s u m s 2$ 的总长度是偶数时，如果我们能够保证：

$\displaystyle len(left\_part) = len(right\_part)$

$\displaystyle max(left\_part) \leq min(right\_part)$

那么中位数就是前一部分的最大值和后一部分的最小值的平均值：

$\displaystyle median = \frac{max(left\_part)+min(right\_part)}{2}$

当 $s u m s 1$ 和 $s u m s 2$ 的总长度是奇数时，如果我们能够保证：

$\displaystyle len(left\_part) = len(right\_part) + 1$

$\displaystyle max(left\_part) \leq min(right\_part)$

那么中位数就是前一部分的最大值和后一部分的最小值的平均值：

$\displaystyle median = max(left\_part)$

对于第一个条件，总长度是偶数和奇数的情况，将两种情况合并。

当 m+n 为偶数： $\displaystyle i+j=m−i+n−j = \frac{m+n}{2} = \frac{m+n+1}{2}$

当 m+n 为奇数： $\displaystyle i+j=m−i+n−j+1 = \frac{m+n+1}{2}$

即：
$\displaystyle j = \frac{m+n+1}{2} - i$

注：规定 $\displaystyle m \leq n（如果不满足 , 就交换 sums1 和 sums2 ）$ 。这样对于任意的 $\displaystyle i \in [0, m]$ ，都有 $\displaystyle j = \frac{m + n + 1}{2} - i \in [0, n]$ 。

第二个条件对于总长度是偶数和奇数的情况是一样的。

$\displaystyle max(left\_part) \leq min(right\_part)$

即：
$\displaystyle sums1[i-1] \leq sums2[j]$
$\displaystyle sums2[j-1] \leq sums1[i]$

因此，在 $\displaystyle [0,m]$ 中找到 $i$ ，使得：

$\displaystyle sums1[i-1] \leq sums2[j]$ 且 $\displaystyle sums2[j-1] \leq sums1[i]$ ，其中 $\displaystyle j = \frac{m + n + 1}{2} - i$

由于 $\displaystyle i \in [0, m]$ ，随着 $i$ 递增， $\displaystyle sums1[i−1]$ 递增， $\displaystyle sums2[j]$ 递减，所以一定存在一个最大的 $i$ 满足 $\displaystyle sums1[i-1] \leq sums2[j]$ 。

即

i + 1

就不满足。将

i + 1

带入，可以得到

\displaystyle sums1[i]> sums2[j-1]

。

因此，此问题转换为，由于 $\displaystyle i \in [0, m]$ 的区间上进行二分搜索，找到最大的 $i$ 值满足 $\displaystyle sums1[i-1] \leq sums2[j]，其中 j = \frac{m + n + 1}{2} - i$ 。

代码

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
           // 确保 m <= n        if (nums1.length > nums2.length) {
               return findMedianSortedArrays(nums2, nums1);        }        int m = nums1.length;        int n = nums2.length;        int left = 0, right = m;        // median1：前一部分的最大值        // median2：后一部分的最小值        int median1 = 0, median2 = 0;        while (left <= right) {
               // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]            // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]            int i = (left + right) / 2;            int j = (m + n + 1) / 2 - i;            // nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]            int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);            int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);            int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);            int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);            if (nums_im1 <= nums_j) {
                   median1 = Math.max(nums_im1, nums_jm1);                median2 = Math.min(nums_i, nums_j);                left = i + 1;            } else {
                   right = i - 1;            }        }        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;      }

复杂度分析