Fork me on GitHub

Leetcode_4.Median of Two Sorted Arrays

这是崔斯特的第十一篇原创文章

参考Median of Two Sorted Arrays

1、题目

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)).

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

2、思路

蛋疼的说,我有看不懂题目了,尤其是O(log (m+n)),啥玩意。没办法,去网上搜索,看看前辈们的想法。

翻译如下:

给你两个排序数组,容量为m的数组A,容量为n的数组B。求出两个数组的中位数(啥玩意?),硬性要求时间复杂度O(log (m+n)).

1:太汗颜了,median到底是个啥,查一下:

中位数是在一组数据中居于中间的数(特别注意的地方是:这组数据之前已经经过升序排列!!!),即在这组数据中,有一半的数据比它大,有一半的数据比它小。如果这组数据包含偶数个数字,中值是位于中间的两个数的平均值。

2:好吧,中位数是这么个玩意,那么理论上首先我们需要先将两个数组合为一,再求这个新合并的数组的中位数。

3:但是,已经限定死了时间复杂度为log(m+n),原来LeetCode的题目也思路不开放嘛。

4:问题可以转化成两个有序序列找第num大的数,由于时间复杂度已经限定死了,只能采用类似二分的思想,每个步骤去掉一半数据元素。

出现了一个词语:时间复杂度,这是个啥?

完全不懂,换个思路来吧,不去看题目了,直接看第四点:

问题可以转化成两个有序序列找第num大的数,由于时间复杂度已经限定死了,只能采用类似二分的思想,每个步骤去掉一半数据元素。

二分,又是二分,赶紧去复习下。

二分查找就是将查找的键和子数组的中间键作比较,如果被查找的键小于中间键,就在左子数组继续查找;如果大于中间键,就在右子数组中查找,否则中间键就是要找的元素。

这个好像还可以看得懂,嘿嘿。我还发现了Python源代码(百度这样说的):

def bin_search(data_list, val):    
    low = 0                         # 最小数下标    
    high = len(data_list) - 1       # 最大数下标    
    while low <= high:        
        mid = (low + high) // 2     # 中间数下标        
        if data_list[mid] == val:   # 如果中间数下标等于val, 返回            
            return mid        
        elif data_list[mid] > val:  # 如果val在中间数左边, 移动high下标            
            high = mid - 1        
        else:                       # 如果val在中间数右边, 移动low下标            
            low = mid + 1    
     return # val不存在, 返回None
ret = bin_search(list(range(1, 10)), 3)
print(ret)

大概明白他的意思了。

3、解法

很多解法都提到:如果我们可以在两个数列中求出第K小的元素,便可以解决该问题

解题思路:这道题要求两个已经排好序的数列的中位数。中位数的定义:如果数列有偶数个数,那么中位数为中间两个数的平均值;如果数列有奇数个数,那么中位数为中间的那个数。比如{1,2,3,4,5}的中位数为3。{1,2,3,4,5,6}的中位数为(3+4)/ 2 = 3.5。那么这题最直接的思路就是将两个数列合并在一起,然后排序,然后找到中位数就行了。可是这样最快也要O((m+n)log(m+n))的时间复杂度,而题目要求O(log(m+n))的时间复杂度。这道题其实考察的是二分查找,是《算法导论》的一道课后习题,难度还是比较大的。

首先我们来看如何找到两个数列的第k小个数,即程序中getKth(A, B , k)函数的实现。用一个例子来说明这个问题:A = {1,3,5,7};B = {2,4,6,8,9,10};如果要求第7个小的数,A数列的元素个数为4,B数列的元素个数为6;k/2 = 7/2 = 3,而A中的第3个数A[2]=5;B中的第3个数B[2]=6;而A[2]<B[2];则A[0],A[1],A[2]中必然不可能有第7个小的数。因为A[2]<B[2],所以比A[2]小的数最多可能为A[0], A[1], B[0], B[1]这四个数,也就是说A[2]最多可能是第5个大的数,由于我们要求的是getKth(A, B, 7);现在就变成了求getKth(A’, B, 4);即A’ = {7};B不变,求这两个数列的第4个小的数,因为A[0],A[1],A[2]中没有解,所以我们直接删掉它们就可以了。这个可以使用递归来实现。

class Solution:
    # @return a float
    # @line20 must multiply 0.5 for return a float else it will return an int
    def getKth(self, A, B, k):
        lenA = len(A); lenB = len(B)
        if lenA > lenB: return self.getKth(B, A, k)
        if lenA == 0: return B[k - 1]
        if k == 1: return min(A[0], B[0])
        pa = min(k/2, lenA); pb = k - pa
        if A[pa - 1] <= B[pb - 1]:
            return self.getKth(A[pa:], B, pb)
        else:
            return self.getKth(A, B[pb:], pa)

    def findMedianSortedArrays(self, A, B):
        lenA = len(A); lenB = len(B)
        if (lenA + lenB) % 2 == 1: 
            return self.getKth(A, B, (lenA + lenB)/2 + 1)
        else:
            return (self.getKth(A, B, (lenA + lenB)/2) + self.getKth(A, B, (lenA + lenB)/2 + 1)) * 0.5

在我提交了代码之后,发现超过50.24 %

我找出最快的解法,来学习下:

class Solution(object):
    def findMedianSortedArrays(self, a, b):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        c = a+b
        c.sort()
        m = len(c) / 2 
        mm = len(c) % 2
        if mm > 0 :
            return c[m]
        return (c[m-1]+c[m])/2.# + (c[m-1]+c[m])%2

第二名的:

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums3 = nums1 + nums2
        nums3.sort()
        l = len(nums3)
        if l%2 == 1:
            return nums3[l/2]
        else:
            return (float(nums3[l/2]) + float(nums3[l/2-1]))/2

每做一题,都会被打击好多次,但是算法是一定要学习的。