Leetcode 2659. Make Array Empty代码超时 求同逻辑时间优化方案

你的代码逻辑没问题，但模拟数组弹出、插入的操作每次都是O(n)复杂度，再加上每次找最小值的O(n)操作，整体O(n²)的时间复杂度在大数据量测试用例下必然超时。

要优化的核心是不用真的模拟数组移动，而是通过数学计算直接累加步数，具体思路和实现如下：

优化思路 #

原逻辑本质是按元素从小到大的顺序依次移除，我们只需要计算每个元素被移除前，从上次移除的位置到当前元素位置需要移动的步数（还要跳过已经被移除的元素），不用实际操作数组。

优化后的代码（并查集实现） #

def countOperationsToEmptyArray(nums):
    n = len(nums)
    # 绑定元素与原始索引，按元素值排序，得到移除顺序
    sorted_pairs = sorted((val, idx) for idx, val in enumerate(nums))
    parent = list(range(n + 1))  # 并查集，n作为哨兵位置
    
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    res = 0
    prev = 0  # 上次移除位置的下一个位置
    for i in range(n):
        val, curr = sorted_pairs[i]
        root = find(curr)  # 找到当前元素对应的第一个未被移除的位置
        if root >= prev:
            res += root - prev + 1
        else:
            # 循环到数组开头，累加从prev到末尾的步数 + 从开头到root的步数
            res += (n - prev) + (root + 1)
        # 标记当前位置已被移除，将其指向后续未被移除的位置
        parent[curr] = find(curr + 1)
        prev = root + 1
    return res

代码说明 #

1. sorted_pairs：把元素和原始索引绑定后排序，明确了元素的移除顺序是从小到大。
2. 并查集：用来快速定位当前元素位置往后第一个未被移除的位置，避免遍历数组。当元素被移除后，将它的父节点指向后续位置，后续查询会自动跳过已移除元素。
3. 步数计算：
   • 如果当前元素的有效位置在prev之后，直接累加root - prev + 1（移动到目标位置+移除的一步）。
   • 如果当前元素的有效位置在prev之前，说明需要先走到数组末尾，再从开头走到目标位置，累加两部分步数。
4. 时间复杂度：排序是O(n logn)，并查集操作近似O(1)（路径压缩优化），整体时间复杂度降到O(n logn)，完全能处理大规模测试用例。

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