如何降低数组清空操作计数代码的时间复杂度？

问题背景 #

给定一个包含不同整数的数组nums，重复执行以下操作直到数组为空：

1. 若首个元素是当前数组的最小值，则移除该元素；
2. 否则将首个元素移至数组末尾。
   返回清空数组所需的总操作次数。

原代码的时间复杂度瓶颈 #

你提供的Java代码采用模拟操作的方式实现，存在两个核心性能问题：

• ArrayList.remove(0)是O(n)操作，每次移除开头元素都要移动后续所有元素；
• 每次移除最小值后，调用find()遍历整个数组找新的最小值，也是O(n)操作。
  整体时间复杂度为O(n²)，当数组长度n较大时（比如1e5级别），会出现严重的性能瓶颈。

优化思路：避免模拟，通过数学计算推导步数 #

核心逻辑是：我们最终是按从小到大的顺序移除元素，只需要跟踪每个元素的原始位置，计算每一步移除时需要的操作次数，无需模拟数组的移动或删除。具体步骤如下：

1. 建立「元素值 → 原始索引」的映射（因为所有元素唯一，可直接用哈希表）；
2. 将数组元素从小到大排序，得到移除元素的顺序；
3. 遍历排序后的元素，计算每一步的操作次数：
   • 记录当前的“起始位置”（上一次移除元素的下一个位置）；
   • 若当前元素的原始索引 ≥ 起始位置：需要从起始位置移动到该索引（pos - start步），加上1步移除；
   • 若当前元素的原始索引 < 起始位置：说明需要绕剩余数组一圈，步数为(剩余数组长度 - start) + pos + 1；
   • 每处理一个元素后，更新起始位置为pos + 1（因为后续元素的位置会因前面的移除左移一位），同时剩余数组长度减1。

优化后的Java代码 #

import java.util.*;

class Solution {
    public long countOperationsToEmptyArray(int[] nums) {
        int n = nums.length;
        // 建立元素到原始索引的映射
        Map<Integer, Integer> valueToIndex = new HashMap<>();
        for (int i = 0; i < n; i++) {
            valueToIndex.put(nums[i], i);
        }
        // 将元素从小到大排序，得到移除顺序
        int[] sortedNums = nums.clone();
        Arrays.sort(sortedNums);
        
        long totalSteps = 0;
        int currentStart = 0;
        int remainingLength = n;
        
        for (int i = 0; i < n; i++) {
            int pos = valueToIndex.get(sortedNums[i]);
            if (pos >= currentStart) {
                // 直接从当前位置走到目标位置，加移除的1步
                totalSteps += pos - currentStart + 1;
            } else {
                // 绕剩余数组一圈，再走到目标位置，加移除的1步
                totalSteps += (remainingLength - currentStart) + pos + 1;
            }
            // 更新起始位置为目标位置的下一位，剩余长度减1
            currentStart = pos + 1;
            remainingLength--;
        }
        return totalSteps;
    }
}

时间复杂度分析 #

• 建立映射：O(n)；
• 排序数组：O(n log n)；
• 遍历计算步数：O(n)；
  整体时间复杂度为O(n log n)，远优于原代码的O(n²)，可以轻松处理大规模输入。

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