Find Kth Number

题目描述

2个array，找第k大的元素

题目列表

• median of two sorted array
• find kth largest elemtn of array

Median of two sorted array

借用find kth的思想，偶数个就要将中间两个平均，奇数就返回中间那个

• 每次在nums1, nums2两个array中各取k/2位置a和b,因为index是0-based,所以index为k/2-1
• 如果有任意一个array的长度小于k/2,那么就可以省去另一个array的前k/2个
• 如果a < b, 那么可以丢掉nums1的前K/2, 反之也是
• 如果a == b,不可以直接返回a，因为也要确定k的奇偶，所以将它和a >= b一起处理

注意点

• 这里a == b的情况
  • 如果k为偶数的话，这种情况下可以return
  • 如果k为奇数的话，这里的a和b都不是第k的元素，而应该是下一个
  • 这里为了code简单，直接传到下一个call中解决

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        n = len(nums1) + len(nums2)
        if n % 2 == 1:
            return self.findKth(nums1, nums2, n / 2 + 1)
        else:
            #偶数个，要取两个值的平均值
            smaller = self.findKth(nums1, nums2, n / 2)
            bigger = self.findKth(nums1, nums2, n / 2 + 1)
            return (smaller + bigger) / 2.0

    def findKth(self, nums1, nums2, k):
        if len(nums1) == 0:
            return nums2[k-1]

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

        if k == 1:
            return min(nums1[0], nums2[0])

        if len(nums1) < k / 2:
            a = None
        else:
            a = nums1[k/2 - 1]

        if len(nums2) < k / 2:
            b = None
        else:
            b = nums2[k/2 - 1]


        if not a:
            return self.findKth(nums1, nums2[k/2:], k - k/2)
        if not b:
            return self.findKth(nums1[k/2:], nums2, k - k/2)
        if a < b:
            return self.findKth(nums1[k/2:], nums2, k - k/2)
        else:
            return self.findKth(nums1, nums2[k/2:], k - k/2)