Kth Largest Element

Question

Find K-th largest element in an array.

Example In array [9,3,2,4,8], the 3rd largest element is 4.

In array [1,2,3,4,5], the 1st largest element is 5, 2nd largest element is 4, 3rd largest element is 3 and etc.

Note You can swap elements in the array

Challenge O(n) time, O(1) extra memory.

Thoughts

sort的方法

一开始看到这道题肯定觉得很简单，只要sort一下，然后return特定index的value就可以了，但是sort的time complexity至少是O（nlogn)

Quick Select

这个是由quick sort演化而来，用到了partition的部分，每次选一个pivot,小于它的放左边，大于它的放右边。

leetcode discuss

So, in the average sense, the problem is reduced to approximately half of its original size, giving the recursion T(n) = T(n/2) + O(n) in which O(n) is the time for partition. This recursion, once solved, gives T(n) = O(n) and thus we have a linear time solution.

Note that since we only need to consider one half of the array, the time complexity is O(n).

If we need to consider both the two halves of the array, like quicksort, then the recursion will be T(n) = 2T(n/2) + O(n) and the complexity will be O(nlogn).

Analysis

kth smallest element 也一样做

Solution

import random
class Solution:
    # @param k & A a integer and an array
    # @return ans a integer
    def kthLargestElement(self, k, A):
        pivot = random.choice(A)
        numSmaller = 0
        length = len(A)
        for idx, num in enumerate(A):
            if num < pivot:
                tmp = A[numSmaller]
                A[numSmaller] = num
                A[idx] = tmp
                numSmaller += 1
        if k < length - numSmaller:
            return self.kthLargestElement(k, A[numSmaller:])
        elif k > length - numSmaller:
            return self.kthLargestElement(k - length + numSmaller, A[:numSmaller])
        return pivot