Python要求O(n)复杂度求无序列表中第K的大元素实例

使用线性时间复杂度 O(n) 求解无序列表中第K大的元素的一种方法是使用快速选择算法，该算法是快速排序的变种。以下是一个 Python 实例代码：

import random

def partition(arr, low, high):
    pivot_index = random.randint(low, high)
    arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def kth_largest_element(arr, k):
    low, high = 0, len(arr) - 1
    while low <= high:
        pivot_index = partition(arr, low, high)
        if pivot_index == len(arr) - k:
            return arr[pivot_index]
        elif pivot_index < len(arr) - k:
            low = pivot_index + 1
        else:
            high = pivot_index - 1

# 示例用法
unsorted_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
k_value = 4
result = kth_largest_element(unsorted_list, k_value)
print(result)

这个算法的平均时间复杂度是 O(n)，最坏情况下为 O(n^2)。然而，由于使用了随机化的划分点选择，通常情况下能够在 O(n) 时间内找到第K大的元素。