Python实现线性时间查找无序序列中第k大元素

可以使用快速选择算法来解决这个问题，该算法是快速排序的变形。快速选择算法的基本思想是，选取一个枢轴元素，将序列中小于枢轴的元素移到左边，大于枢轴的元素移到右边，然后判断枢轴的位置和第k大的位置的大小关系，如果相等则返回枢轴元素，否则根据枢轴位置和k的大小关系缩小搜索范围。具体实现如下：

def findKthLargest(nums, k):
    '''
    :type nums: List[int]
    :type k: int
    :rtype: int
    '''
    n = len(nums)
    left, right = 0, n - 1
    while True:
        pos = partition(nums, left, right)
        if pos == k - 1:
            return nums[pos]
        elif pos > k - 1:
            right = pos - 1
        else:
            left = pos + 1

def partition(nums, left, right):
    pivot = nums[left]
    while left < right:
        while left < right and nums[right] <= pivot:
            right -= 1
        nums[left] = nums[right]
        while left < right and nums[left] >= pivot:
            left += 1
        nums[right] = nums[left]
    nums[left] = pivot
    return left

其中，findKthLargest函数用于查找第k大的数，partition函数用于实现快速选择算法中的分区操作。时间复杂度为O(n)，空间复杂度为O(1)。