题目
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)
