LeetCode 4 Median of Two Sorted Arrays 解題報告

原文連結: http://hankerzheng.com/blog/LeetCode-Median-of-Two-Sorted-Arrays

Problem Description

LeetCode 4 Median of Two Sorted Arrays

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

Examples:

nums1 = [1, 3]

nums2 = [2]

The median is 2.0

nums1 = [1, 2]

nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

中文大意:

給定兩個排好序的數組, 求數組合并後的中位數, 要求在O(log (m+n))時間複雜度内完成

My Solution

因為時間複雜度是

log

級别的, 是以我們很容易就想到采用

binary search

來做, 但是怎麼将求中位數轉化為

binary search

呢? 本題目的基本概念就是

求中位數 => 求第k大的數

.

注意: 我們用

rank

表示一個數在數列中的大小的排序序号. 對于一個已經排序的數組

nums

, 我們可以說

nums[rank-1]

是數組

nums

中第

rank

小的數. 也就是說,

rank

是1-based index(以

1

為起始序号的标号方式).

由此我們可以得到一個定理, 假設我們在有序數列

nums1

中找到了

rank1

的數, 在有序數列

nums2

中找到了

rank2

的數, 并且有

nums1[k1 - 1] < nums2[k2 - 1]

, 那麼

nums[k2 - 1]

的

rank

至少為

rank1 + rank2

,

nums1[k1 - 1]

的

rank

至多為

rank1 + rank2 - 1

.

這個定理也可以推廣到

n

個有序數列中:

假設存在

n

個有序數列

nums1

,

nums2

, …,

numsn

, 并且我們已知一組元素:

{nums1[rank1-1], nums2[rank2-1], ..., numsn[rankn-1]}

.

其中, 所有已知元素中的最大值為

numsMax[rankMax-1]

, 所有已知元素最小值為

numsMin[rankMin-1]

, 那麼我們有:

-

numsMax[rankMax-1]

在所有數中的

rank

至少為

rank1 + rank2 + rank3 + ... + rankn

-

numsMin[rankMin-1]

在所有數中的

rank

至多為

rank1 + rank2 + rank3 + ... + rankn - n + 1

.

利用這個定理, 我們就可以求得兩個有序數列中第

k

大的數:

- 先将

k

平分成兩部分,

k = k1 + k2

- 判斷

nums1[k1]

和

nums2[k2]

的大小, 較小的那個數的

rank

至多為

k-1

- 縮減搜尋空間, 繼續搜尋

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        length = len(nums1) + len(nums2)
        leftRank = (length + ) / 
        rightRank = (length + ) / 
        return self.getRank(nums1, , nums2, , leftRank) /  + self.getRank(nums1, , nums2, , rightRank) /  

    def getRank(self, nums1, start1, nums2, start2, rank):
        if len(nums1) - start1 > len(nums2) - start2:
            return self.getRank(nums2, start2, nums1, start1, rank)
        elif len(nums1) - start1 <= :
            return nums2[start2 + rank - ]
        elif rank == :
            return min(nums1[start1], nums2[start2])

        rank1 = min(rank / , len(nums1) - start1)
        rank2 = rank - rank1
        if nums1[start1 + rank1 - ] > nums2[start2 + rank2 - ]:
            return self.getRank(nums1, start1, nums2, start2 + rank2, rank - rank2)
        elif nums1[start1 + rank1 - ] < nums2[start2 + rank2 - ]:
            return self.getRank(nums1, start1 + rank1, nums2, start2, rank - rank1)
        else:
            return nums1[start1 + rank1 - ]
           

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length = nums1.length + nums2.length;
        int leftRank = (length + ) / ; // Rank is 1-base index
        int rightRank = (length + ) / ; // Rank is 1-base index
        return getRank(nums1, , nums2, , leftRank) / 
            + getRank(nums1, , nums2, , rightRank) / ;
    }

    public int getRank(int[] nums1, int start1, int[] nums2, int start2, int rank){
        if (nums1.length - start1 > nums2.length - start2){
            return getRank(nums2, start2, nums1, start1, rank);
        }else if (start1 >= nums1.length){
            return nums2[start2 + rank - ];
        }else if (rank == ){
            return Math.min(nums1[start1], nums2[start2]);
        }

        int rank1 = Math.min(rank / , nums1.length - start1);
        int rank2 = rank - rank1;

        if(nums1[start1 + rank1 - ] > nums2[start2 + rank2 - ]){
            return getRank(nums1, start1, nums2, start2 + rank2, rank - rank2);
        }else if (nums1[start1 + rank1 - ] == nums2[start2 + rank2 - ]){
            return nums1[start1 + rank1 - ];
        }else{
            return getRank(nums1, start1 + rank1, nums2, start2, rank - rank1);
        }

    }
}