"""
QUESTION:
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.

Note:
You may assume k is always valid, 1 <= k <= array's length.
ANSWER:
quick select
"""

import random
class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {integer}
    def findKthLargest(self, nums, k):
        def dfs(l,r,k):
            if not (l<=k<=r):
                return None
            if l == r:
                return nums[k]
            pivot = l + random.randrange(r-l+1)
            nums[r], nums[pivot] = nums[pivot], nums[r]
            pivot = l
            for i in xrange(l,r):
                if nums[i] < nums[r]:
                    nums[pivot], nums[i] = nums[i], nums[pivot]
                    pivot += 1
            nums[pivot], nums[r] = nums[r], nums[pivot]
            if pivot == k:
                return nums[pivot]
            elif pivot < k:
                return dfs(pivot+1,r,k)
            else:
                return dfs(l,pivot-1,k)
        return dfs(0,len(nums)-1,len(nums)-k)

    def findKthLargest_2(self, nums, k):
        nums = sorted(nums)
        return nums[len(nums)-k]

if __name__ == '__main__':
    print Solution().findKthLargest_2([3,2,1,5,6,4],1)