Median of Two Sorted Arrays

jidibinlin included in leetcode divide-and-conquer

2022-10-04 667 words 4 minutes views

Contents

Description

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Example 1:

1
2
3


Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

1
2
3


Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

1
2


Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Example 4:

1
2


Input: nums1 = [], nums2 = [1]
Output: 1.00000

Example 5:

1
2


Input: nums1 = [2], nums2 = []
Output: 2.00000

Constraints:

1
2
3
4
5
6


nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

Analyse

这道题最简单的想法就是先归并到一个数组，然后再把中位数找到，但是此时的时间复杂度为\(o(m+n)\) 不符合题意。题目要求的是 \(o(\log(m+n))\) 。此时我们能想到的应该就只有二分法了，对于有序数组，二分法总能非常有效的降低算法的复杂度。但是如何二分成为一个问题。中位数指的是一个数列中间的数。设 len = len(array) 这里的/为整除

\begin{equation} \label{中位数公式} medium =\begin{cases} \dfrac{array[len/2-1] + array[len/2]}{2} \qquad &len\mod 2=0 && \\ \dfrac{array[len/2-1]}{2} \qquad &len\mod 2\neq 0 \end{cases} \end{equation}

这道题是寻找两个有序数组的中位数，我们可以姑且假设他们已经合并后的数组为 nums3*我们要在nums3中寻找中位数。此时 *nums3 的长度我们是知道的(m+n) 那么其中位数的应该为第 k= \(\frac{m+n}{2}\) 个数（这里我们先只看奇数情况。这时我们可以对k进行二分处理，分别找到两个s数组中第\(\frac{k}{2}\) 个数进行比较，然后排除较小的以及它所在数组中在它前面的数。因为他们是不可能成为中位数的。对于 nums1[k/2-1] 和nums2[k/2-1] 在它们之前的只有 k/2-1 + k/2-1 = k -2 个数。即使算上较小的那个数，也只能到第k-1个数。所以他们是不可能成为第k个数的。这时我们让 k = k-A(A为已经排除的数的个数) 然后继续对剩下的数组进行同样的操作。这里会出现两种情况

如果 nums1[k/2-1] >= nums2[k/2-1] 则直接排除nums1[k/2-1] 及其前面的数
如果 nums1[k/2-1] < nums2[k/2-1] 则直接排除nums2[k/2-1] 及其前面的数

在排除过程中我们还会遇到几种情况

k/2-1 越界，这种情况取最后一个元素
k=1 直接返回较小的元素
数组为空，直接去非空数组中寻找即可

Implement

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64


//c++ version
#include <iostream>
#include <vector>
#include <algorithm>

int main(int argc, char *argv[]) {
    Solution s;
    vector<int> nums1 = new vector<int>();
    vector<int> nums2 = new vector<int>();

    for(int i = 1;i<10;i++){
        nums1.push_back(i);
    }
    for(int i= 1;i<10;i=i+2){
        nums2.push_back(i);
    }

    s.findMedianSortedArrays(nums1,nums2);
    return 0;
}

class Solution {
public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
        int k = nums1.size() + nums2.size();
        if(k%2 == 0){
            return min(getKthElement(nums1, nums2, k/2+1),getKthElement(nums1, nums2,k/2))/2.0;
        }else{
            return getKthElement(nums1,nums2,k/2);
        }
    }

    double getKthElement(vector<int> &nums1, vector<int> &nums2,int k){
        int index1 = 0;
        int index2 = 0;

        int m = nums1.size();
        int n = nums2.size();

        while (true){
            if (index1 == m){
                return nums2[index2+k-1];
            }
            if(index2 == n){
                return nums1[index1 +k -1];
            }
            if(k == 1){
                return min(nums1[index1],nums2[index2]);
            }

            int newIndex1 = min(index1+k/2-1,m-1);
            int newIndex2 = min(index2+k/2-1,n-1);

            if(nums1[newIndex1] >= nums2[newIndex2]){
                k -= newIndex2 - index2 +1;
                index2 = newIndex2+1;
            }else{
                k -= newIndex1 - index1 +1;
                index1 = newIndex1+1;
            }

        }
    }
};

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58


//GO version
package main

import (
    "fmt"
    "math"
)

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    k := int(math.Ceil((float64(len(nums1)) + float64(len(nums2))) / 2))

    if (len(nums1)+len(nums2))%2 == 0 {
        foo1 := getKthElement(nums1, nums2, k)
        foo2 := getKthElement(nums1, nums2, k+1)
        return float64(foo1+foo2) / 2
    } else {
        return float64(getKthElement(nums1, nums2, k))
    }

}

func getKthElement(nums1 []int, nums2 []int, k int) int {
    if len(nums1) == 0 {
        return nums2[k-1]
    }

    if len(nums2) == 0 {
        return nums1[k-1]
    }

    compareIdx := k / 2

    if compareIdx == 0 {
        return min(nums1[0], nums2[0])
    }

    nums1Idx := min(len(nums1)-1, compareIdx-1)
    nums2Idx := min(len(nums2)-1, compareIdx-1)

    if nums1[nums1Idx] >= nums2[nums2Idx] {
        if len(nums2) <= compareIdx {
            return getKthElement(nums1, []int{}, k-(nums2Idx+1))
        }
        return getKthElement(nums1, nums2[compareIdx:], k-(nums2Idx+1))
    } else {
        if len(nums1) <= compareIdx {
            return getKthElement([]int{}, nums2, k-(nums1Idx+1))
        }
        return getKthElement(nums1[compareIdx:], nums2, k-(nums1Idx+1))
    }
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

summery

这道题对二分的运用比较灵活，主要是二分的对象变了，但是思想还在。正常的二分是对数组的长度进行二分，而此题的二分却是先确定中位数的位置，再利用二分的思想去到两个数组中分别寻找排除，非常巧妙，受益匪浅。