QuickSort的好哥们QuickSelect

第k大元素

在数组中找到第k大的元素。

样例

给出数组 [9,3,2,4,8]，第三大的元素是 4

给出数组 [1,2,3,4,5]，第一大的元素是 5，第二大的元素是 4，第三大的元素是 3，以此类推。

挑战

要求时间复杂度为O(n)，空间复杂度为O(1)。

注意事项

你可以交换数组中的元素的位置。

代码：

import random
class Solution:
    def kthLargestElement(self, k, A):
        middle = random.randint(0, len(A)-1)
        A_big = []
        A_small = []
        num = 0
        for index in range(0, len(A)):
            if(A[index]>A[middle]):
                A_big.append(A[index])
            elif(A[index]==A[middle]):
                num=num+1
            elif(A[index]<A[middle]):
                A_small.append(A[index])
        if(len(A_big)==k-1):
            return A[middle]
        elif(len(A_big)>k-1):
            return self.kthLargestElement(k, A_big)
        elif(len(A_big)<k-1):
            return self.kthLargestElement(k-len(A_big)-num, A_small)

QuickSelect很容易理解，就是使用QuickSort的思想。

另外，QuickSort学习可以参考这个：

https://blog.csdn.net/u013309870/article/details/68921848

附上题目来源：

https://www.lintcode.com/problem/kth-largest-element/description