难度: 中等(Medium)

题目

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] and k = 2, return 5.

思路

利用快速排序的思想，用数组头将数组两分，左边比它小，右边比它大。如果这个元素正好是第k个，直接返回；如果比k大，则从比它小的那些数中找出第k大的；否则，从比它大的数中找出相应的数字。

代码

class Solution(object):

    def quick_sort(self, nums, k):
        i = 0
        for j in range(1,len(nums)):
            if nums[j] > nums[0]:
                i += 1
                nums[i],nums[j] = nums[j],nums[i]
        nums[i],nums[0] = nums[0],nums[i]
        if i == k-1:
            return nums[i]
        elif i > k-1:
            return self.quick_sort(nums[:i], k)
        else:
            return self.quick_sort(nums[i+1:], k-i-1)

    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if nums==None or len(nums)==0 or k<1:
            return -1
        return self.quick_sort(nums, k)