O(n)算法查找数字集合的中位数

要使用O(n)算法查找数字集合的中位数，您可以使用线性时间选择算法（Linear Time Selection Algorithm），也称为快速选择算法（Quickselect Algorithm）。以下是一个示例的快速选择算法实现：

def find_median(nums):
    n = len(nums)
    k = (n + 1) // 2  # 中位数的位置

    def partition(left, right):
        pivot = nums[right]  # 选择最右边的元素作为枢轴
        i = left - 1

        for j in range(left, right):
            if nums[j] <= pivot:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]

        nums[i + 1], nums[right] = nums[right], nums[i + 1]
        return i + 1

    def quick_select(left, right):
        if left == right:
            return nums[left]

        pivot_index = partition(left, right)

        if k == pivot_index + 1:
            return nums[pivot_index]
        elif k < pivot_index + 1:
            return quick_select(left, pivot_index - 1)
        else:
            return quick_select(pivot_index + 1, right)

    return quick_select(0, n - 1)

在上面的示例中，find_median函数接受一个数字集合nums作为输入，并使用快速选择算法来查找中位数。算法的核心是通过选择枢轴元素将集合划分为两个部分，然后根据中位数的位置递归地在其中一个部分中继续查找，直到找到中位数。

要使用该算法，只需调用find_median函数并传入数字集合。它将返回集合的中位数。

请注意，快速选择算法的平均时间复杂度为O(n)，但最坏情况下的时间复杂度为O(n^2)。然而，在实践中，它通常表现良好，并且在大多数情况下能够以线性时间找到中位数。