k-O(n) 中数组中的最小元素

Question

是否有可能在时间 O(n) 内返回未排序数组中的 k-最小整数，其中 n 是数组的大小？假设我们返回答案的顺序无关紧要。有些方法使用有序数据结构（如堆）在 O(n log k) 时间内完成此任务，但我认为我们可以通过修改在 O(n) 时间内快速选择。这样对吗？

Answer 1

是的，使用对 Quickselect 算法的修改，也称为 QuickSort 变体，平均可以在 O(n) 时间内返回未排序数组中的 k-最小整数。 Quickselect 是一种用于查找无序列表中第 k 个最小元素的高效算法。您可以对 Quickselect 进行的修改是跟踪分区过程中遇到的 k-smallest 元素，而不是仅查找第 k-th 最小元素。

这里是修改后的 Quickselect 算法的伪代码：

function modified_quickselect(arr, k)
    if k == 0
        return []
    if k >= length(arr)
        return arr

    return quickselect_helper(arr, 0, length(arr) - 1, k)

function quickselect_helper(arr, left, right, k)
    if left == right
        return arr[:k]

    pivot_index = select_pivot_index(arr, left, right)
    pivot_index = partition(arr, left, right, pivot_index)

    if k == pivot_index
        return arr[:k]
    elseif k < pivot_index
        return quickselect_helper(arr, left, pivot_index - 1, k)
    else
        left_part = arr[:pivot_index]
        right_part = quickselect_helper(arr, pivot_index + 1, right, k - pivot_index)
        return left_part + right_part

function partition(arr, left, right, pivot_index)
    pivot = arr[pivot_index]
    swap(arr[pivot_index], arr[right]) // Move pivot to end

    store_index = left
    for i in range(left, right)
        if arr[i] < pivot
            swap(arr[store_index], arr[i])
            store_index += 1

    swap(arr[right], arr[store_index]) // Move pivot to its final place
    return store_index

function select_pivot_index(arr, left, right)
    // This function can be implemented in several ways, such as choosing the first element,
    // a random element, or the median of three elements.
    // For simplicity, we can just return the left index in this example.
    return left

修改后的Quickselect算法的平均时间复杂度为O(n)，但在最坏情况下，它可能需要O(n^2)时间，具体取决于pivot选择策略。然而，使用一个好的枢轴选择方法（例如，中位数的中位数）可以保证 O(n) 的最坏情况时间复杂度。

请注意，提供的伪代码并未针对处理重复项进行优化。如果您需要有效地处理重复项，您可能需要相应地修改分区函数。