Kth Largest Element in an Array

题目描述

In an array, find kth largest element.

解题方法

1. 先sort, 时间复杂度O(nlogn)

2. 利用quick select的思想，就是quick sort之前的partition部分

3. 如果是kth largest,就把大的放在左边

4. 如果是kth smallest,就把小的放在左边
5. 用左边的值来判断是第几个（其实用右边也可以）

多写几遍！自己记牢！

Solution

def findKthLargest(nums):
    length = len(nums)
    if length == 0:
        return 

    left = 0
    right = length - 1
    pivot = nums[0] # 就用第一个做pivot
    index = 0 # 指针

    while index <= right: # 注意终止条件是小于等于，因为right指的可能放下一个大数的地方
        if nums[index] < pivot:
            nums[left], nums[index] = nums[index], nums[left]
            left += 1
            index += 1
        elif nums[index] == pivot:
            index += 1
        else:
            nums[right], nums[index] = nums[index], nums[right]
            right -= 1
            index += 1

    # 因为是0-based的，所以left+1是pivot的次序
    if left + 1 == k:
        return pivot
    elif left + 1 > : # kth在左边的subarray里
        return self.findKthLargest(nums[:left+1], k) # 可以不用包含left+1这个等于的数
    else: # kth在右边的subarray里，可以去掉左边的数了
        return self.findKthLargest(nums[left+1:], k - left - 1) # 包含第left+1个，左边有 left - 0 + 1个数

Reference