Find Kth Largest Element in an Array

题目描述

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example, Given [3,2,1,5,6,4]`` andk = 2, return5`.

Note: You may assume k is always valid, 1 ≤ k ≤ array's length.

解题方法

brute force

sort, 然后取kth largest

O(nlogn)

quick select

Quick select的经典应用， average case O(n), worest case O(n^2)

要把quick select的方法练透，写出自己的模板

我这里直接将比pivot大的放到前面，这样直接用前面一个指针计算第n大，不用再跟 长度相减。 如果是求kth smallest,就应该将小的放前面

注意点

  • pivot选择
  • 大小元素的放置
  • 重复元素的处理

Solution

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        length = len(nums)
        if length == 0:
            return
        pivot = nums[0]
        left = 0 
        right = length - 1
        p = 0
        while p <= right:
            if nums[p] > pivot:
                self.swap(nums, left, p) 
                p += 1
                left += 1
            elif nums[p] == pivot:
                p += 1
            else:
                self.swap(nums, right, p)
                right -= 1

        if left + 1 == k:
            return pivot
        elif left + 1< k:
            return self.findKthLargest(nums[left+1:], k - left - 1)
        else:
            return self.findKthLargest(nums[:left+1], k)

    def swap(self, nums, p1, p2):
        tmp = nums[p2]
        nums[p2] = nums[p1]
        nums[p1] = tmp

Reference