数组重复元素归约处理：O(n²)代码超时的优化方案咨询

问题描述 #

给定一个数值数组，重复执行以下归约操作直至无重复非0元素：

• 找出所有至少出现2次的元素，选取值最大的那个元素的首次出现的两个有效位置
• 标记第一个位置的元素为无效（逻辑删除），将第二个位置的元素除以2（向下取整）并更新
• 重复上述步骤

示例输入：[2,1,5,10,10,1]，最终结果：[0,1]

约束：数组长度1_{10^5，元素值1}10^9

原代码的性能瓶颈 #

原代码采用每次循环全量遍历数组查找重复元素，且使用ArrayList的remove操作（时间复杂度O(n)），导致整体时间复杂度为O(n²)，在数组长度为10^5时会超时。

优化方案 #

核心思路 #

1. 逻辑删除替代物理删除：用标记数组记录元素是否有效，避免物理删除带来的索引移动开销
2. 大顶堆维护待处理元素：优先处理值最大的重复元素，符合原逻辑且快速获取目标元素
3. 哈希表跟踪元素索引：用哈希表存储每个值对应的有效索引队列，快速定位重复元素的位置

Java实现代码 #

import java.util.*;

public class ArrayReduction {
    public static void main(String[] args) {
        System.out.println(solve(Arrays.asList(2, 1, 5, 10, 10, 1))); // 输出[0,1]
    }

    public static List<Integer> solve(List<Integer> arr) {
        int n = arr.size();
        int[] elements = new int[n];
        boolean[] valid = new boolean[n];
        // 初始化元素和有效标记
        for (int i = 0; i < n; i++) {
            elements[i] = arr.get(i);
            valid[i] = true;
        }

        // 哈希表：值 -> 有效索引队列
        Map<Integer, Queue<Integer>> valueIndices = new HashMap<>();
        // 大顶堆，存储当前存在重复的元素值（去重）
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // 初始化哈希表和堆
        for (int i = 0; i < n; i++) {
            int val = elements[i];
            valueIndices.computeIfAbsent(val, k -> new LinkedList<>()).offer(i);
        }
        // 找出初始的重复元素加入堆
        for (Map.Entry<Integer, Queue<Integer>> entry : valueIndices.entrySet()) {
            if (entry.getValue().size() >= 2) {
                maxHeap.offer(entry.getKey());
            }
        }

        while (!maxHeap.isEmpty()) {
            int currentMax = maxHeap.poll();
            Queue<Integer> indices = valueIndices.get(currentMax);
            if (indices == null || indices.size() < 2) {
                continue; // 该元素已无足够有效索引，跳过
            }

            // 获取前两个有效索引
            int idx1 = -1;
            while (!indices.isEmpty() && !valid[indices.peek()]) {
                indices.poll(); // 移除无效索引
            }
            if (indices.isEmpty()) {
                valueIndices.remove(currentMax);
                continue;
            }
            idx1 = indices.poll();

            int idx2 = -1;
            while (!indices.isEmpty() && !valid[indices.peek()]) {
                indices.poll();
            }
            if (indices.isEmpty()) {
                // 只剩一个有效索引，放回队列
                indices.offer(idx1);
                valueIndices.put(currentMax, indices);
                continue;
            }
            idx2 = indices.poll();

            // 标记idx1为无效
            valid[idx1] = false;
            // 更新idx2的值为currentMax/2
            int newVal = currentMax / 2;
            elements[idx2] = newVal;

            // 处理新生成的值
            if (newVal > 0) {
                valueIndices.computeIfAbsent(newVal, k -> new LinkedList<>()).offer(idx2);
                // 如果新值现在有至少两个有效索引，加入堆（去重）
                if (valueIndices.get(newVal).size() >= 2) {
                    maxHeap.offer(newVal);
                }
            }

            // 更新原currentMax的队列，如果还有剩余有效索引，放回哈希表，若仍有重复则重新加入堆
            if (!indices.isEmpty()) {
                valueIndices.put(currentMax, indices);
                if (indices.size() >= 2) {
                    maxHeap.offer(currentMax);
                }
            } else {
                valueIndices.remove(currentMax);
            }
        }

        // 收集所有有效元素
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (valid[i]) {
                result.add(elements[i]);
            }
        }
        return result;
    }
}

复杂度分析 #

• 时间复杂度：O(n logn)。初始化哈希表和堆为O(n)，每个元素最多被处理O(logV)次（V为初始元素最大值，每次除以2，最多log₂(1e9)≈30次），每次堆操作是O(logn)，总操作次数为O(n logV)，近似O(n logn)
• 空间复杂度：O(n)，用于存储元素数组、有效标记数组、哈希表和堆

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