LeetCode 4. 寻找两个有序数组的中位数（难）

折半查找（二分查找）的时间复杂度是 \(O(log_2\ n)\)，也就是 \(O(log\ n)\)。

题目

给定两个大小为 m 和 n 的有序数组 nums1和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m+n))。

你可以假设 nums1和 nums2 不会同时为空。

示例

示例一 

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

则中位数是 2.0
示例 2:
示例二 
1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

考察知识点

折半查找、边界判定、无尾递归

核心思想

参考链接

将两个有序数组重组，求中位数。 将问题 转化为在两个数组中找第 K 个小的数 。 求中位数，其实就是求第 k 小数的一种特殊情况。 首先在两个数组中分别找出第k/2 大的数，再比较这两个第 k/2 大的数，这里假设两个数组为 A ，B。 那么比较结果会有下面几种情况： - A[k/2] = B[k/2],那么第 k 大的数就是 A[k/2] - A[k/2] > B[k/2],那么第 k 大的数肯定在 A[0:k/2+1] 和 B[k/2:] 中，这样就将原来的所有数的总和减少到一半了，再在这个范围里面找第 k/2 大的数即可，这样也达到了二分查找的区别了。 - A[k/2] < B[k/2]，那么第 k 大的数肯定在 B[0:k/2+1]和 A[k/2:] 中，同理在这个范围找第 k/2 大的数就可以了。 反复递归执行上述过程即可

Python版本

不满足算法复杂度的一个版本

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
# coding: utf-8
class Solution:
    # 冒泡排序1    
    def bubbleSort(self, alist: list)  -> list:
        list_len = len(alist)
        exchange = False
        for i in range(list_len-1, 0, -1):  # 从后往前遍历
            for j in range(0, i):  # 从前往后遍历
                if alist[j] > alist[j+1]:  # 如果前面的比后面的大
                    alist[j], alist[j+1] = alist[j+1], alist[j]
                    exchange = True
            # 一次内层循环确定之后就判断一下是不是交换了，没有交换就说明顺序全部正确
            if not exchange:
                break
        return alist

    def findMedianSortedArrays(self, nums1: list, nums2: list) -> float:
        # step1 合并两个list
        sum_list = nums1 + nums2
        # step2 对合并list排序
        sum_list = self.bubbleSort(sum_list)
        # step3 输出中间值
        list_length = len(sum_list)
        k = int(list_length/2)
        if list_length%2==0:  # 偶数个数字
            mid_num1 = sum_list[k-1]
            mid_num2 = sum_list[k]
            mid_num = float(mid_num1+mid_num2)/2 
        else:  # 奇数个数字
            mid_num = float(sum_list[k])
        
        return mid_num

print("leet code accept!!!")
nums1 = [[1, 3, 4, 7]]
nums2 = [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]
Answer = [4.5]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(nums1)):
        result = solution.findMedianSortedArrays(nums1[i], nums2[i])
        print(result==Answer[i])

满足O(log(m+n))复杂度的一个算法

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
class Solution:
    def findMedianSortedArrays(self, nums1: list, nums2: list) -> float:
        n = len(nums1)
        m = len(nums2)
        left = int((n + m + 1) / 2)  # 要找的前一个数字
        right = int((n + m + 2) / 2)  # 要找的后一个数字    
    
        # 一个小技巧：将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
        return (self.getKth(nums1, 0, n-1, nums2, 0, m-1, left) + self.getKth(nums1, 0, n-1, nums2, 0, m-1, right)) * 0.5

    def getKth(self, nums1: list, start1: int, end1: int, nums2: list, start2: int, end2: int, k: int):
        len1 = end1 - start1 + 1
        len2 = end2 - start2 + 1
        # 让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
        if(len1>len2):
            return self.getKth(nums2, start2, end2, nums1, start1, end1, k)
        if(len1==0):
            return nums2[start2+k-1]
        if(k==1):
            return min(nums1[start1], nums2[start2])

        i = int(start1 + min(len1, k/2) - 1)  # 从start开始往后 取k/2个数字
        j = int(start2 + min(len2, k/2) - 1)
        
        if(nums1[i] > nums2[j]):
            return self.getKth(nums1, start1, end1, nums2, j+1, end2, k-(j-start2+1))
        else:
            return self.getKth(nums1, i+1, end1, nums2, start2, end2, k-(i-start1+1))
        

print("leet code accept!!!")
nums1 = [[1, 3, 4, 7], [1, 2, 3]]
nums2 = [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [4, 5, 6, 7, 8, 9]]
Answer = [4.5, 5]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(nums1)):
        print("-"*50)
        result = solution.findMedianSortedArrays(nums1[i], nums2[i])
        # print(result)
        # print(Answer[i])
        print(result==Answer[i])
  • 上述算法的时空复杂度分析

时间复杂度：每进行一次循环，减少 k/2 个元素，所以时间复杂度是 O(log(k)，而 k = (m+n) / 2，所以最终的复杂也就是 O(log(m+n）。

空间复杂度：虽然用到了递归，但是可以看到这个递归属于尾递归（见通用算法知识），所以编译器不需要不停地堆栈，所以空间复杂度为 O(1)。

有效语法糖

1、python3的range函数实现从后往前循环

1
2
3
a = list(range(9, 0, -1))  # range(start: int, stop: int, step: int)
print(a)
[output] [9, 8, 7, 6, 5, 4, 3, 2, 1]