如何无复制传递Python列表切片？快速选择O(n)复杂度问题

你的思路完全没问题，但切片操作确实是个坑——每次arr[:p]或者arr[p:]都会生成原列表的副本，这直接让时间复杂度从预期的O(n)飙升到O(n log n)（甚至更糟），因为每次复制都要花费和切片长度成正比的时间。

要解决这个问题，核心思路是在原数组上操作，通过传递左右边界索引来限定处理范围，完全避免复制数组。下面是修改后的实现：

def partition(arr, left, right):
    # 选择当前区间的最后一个元素作为基准
    pivot_val = arr[right]
    pivot_idx = left  # 基准最终要放置的位置
    
    for i in range(left, right):
        if arr[i] < pivot_val:
            # 把小于基准的元素移到基准位置的左侧
            arr[i], arr[pivot_idx] = arr[pivot_idx], arr[i]
            pivot_idx += 1
    # 把基准元素放到正确的位置
    arr[right], arr[pivot_idx] = arr[pivot_idx], arr[right]
    return pivot_idx

def quickselect(k, arr):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        pivot_pos = partition(arr, left, right)
        
        if pivot_pos == k:
            # 找到第k个元素（0-based）
            return arr[k]
        elif pivot_pos > k:
            # 目标在基准左侧，缩小右边界
            right = pivot_pos - 1
        else:
            # 目标在基准右侧，缩小左边界
            left = pivot_pos + 1
    # 如果k超出数组范围（理论上不会发生，前提是k合法）
    return None

关键修改点说明： #

• Partition函数：新增left和right参数，限定只在数组的[left, right]区间内进行分区操作，全程操作原数组，没有任何复制。
• Quickselect函数：不再生成子数组，而是通过调整left和right边界来缩小搜索范围，每次迭代只处理原数组的一部分，时间复杂度保持O(n)（平均情况）。
• 边界处理：循环条件left <= right确保不会遗漏任何元素，当基准位置等于k时直接返回结果，否则根据基准和k的大小关系调整边界。

测试示例： #

arr = [3, 1, 4, 1, 5, 9, 2, 6]
print(quickselect(3, arr))  # 输出3（对应排序后数组的第4个元素，0-based索引3）

这样修改后，算法就真正实现了O(n)的平均时间复杂度，完全避免了切片带来的额外开销。

内容的提问来源于stack exchange，提问作者Pythoner