数组元素处理耗时求和：时间复杂度分析与优化需求

原代码的时间复杂度 #

原代码用队列模拟处理流程，每个元素的每一次“减1”操作都会执行出队、处理、入队（未完成时）的操作。总操作次数等于数组所有元素的和 S = sum(arr)，因此时间复杂度为 O(S)。

这种实现的致命问题是：当数组包含大量大数值元素时（比如1e5个值为1e4的元素），S会达到1e9，O(1e9)的操作次数完全无法在合理时间内完成，必然超时。

优化方案：数学推导 + 高效统计 #

我们可以通过数学分析跳过模拟每一步操作，将时间复杂度降到O(n log n)，完美适配题目约束。

核心思路 #

每个元素的完成时间由两部分组成：

1. 前(a_i - 1)轮的总处理时间（每轮处理的元素数为当前未完成的元素数量）
2. 该元素在第a_i轮中的处理位置（严格遵循初始数组的顺序）

把所有元素的完成时间相加，就是最终结果。

具体步骤 #

1. 计算前k轮的总时间和

• 先统计每个数值的出现频率freq[v]
• 用后缀和计算cnt[v]：表示数组中值≥v的元素数量
• 用前缀和计算sum_cnt[v]：表示前v轮的总处理时间（即sum_{k=1到v} cnt[k]）

对于值为a_i的元素，前(a_i-1)轮的总时间就是sum_cnt[a_i - 1]。

2. 计算元素在对应轮次的处理位置

元素在第a_i轮的处理位置，等于初始数组中索引≤i且值≥a_i的元素数量（第a_i轮只处理未完成元素，且保持初始顺序）。

我们可以通过以下方式高效统计：

• 将元素按值从大到小排序（值相同则按索引从小到大）
• 使用树状数组（Fenwick Tree）记录已处理元素的索引，遍历排序后的元素时，查询前缀和即可得到当前元素的位置。

实现代码示例 #

import java.util.*;

public class Solution {
    static class FenwickTree {
        private int[] tree;
        private int n;

        public FenwickTree(int size) {
            n = size;
            tree = new int[n + 1]; // 索引从1开始
        }

        public void update(int idx, int delta) {
            idx++; // 转换为1-based索引
            while (idx <= n) {
                tree[idx] += delta;
                idx += idx & -idx;
            }
        }

        public int query(int idx) {
            idx++; // 转换为1-based索引
            int sum = 0;
            while (idx > 0) {
                sum += tree[idx];
                idx -= idx & -idx;
            }
            return sum;
        }
    }

    public long solve(int[] arr) {
        int n = arr.length;
        if (n == 0) return 0;

        // 步骤1：统计频率、cnt数组、sum_cnt数组
        int maxA = Arrays.stream(arr).max().getAsInt();
        int[] freq = new int[maxA + 2];
        for (int num : arr) {
            freq[num]++;
        }

        int[] cnt = new int[maxA + 2];
        for (int v = maxA; v >= 1; v--) {
            cnt[v] = cnt[v + 1] + freq[v];
        }

        long[] sum_cnt = new long[maxA + 2];
        for (int v = 1; v <= maxA; v++) {
            sum_cnt[v] = sum_cnt[v - 1] + cnt[v];
        }

        // 步骤2：计算每个元素的pos_i
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }

        // 按值从大到小排序，值相同则索引从小到大
        Arrays.sort(indices, (i1, i2) -> {
            if (arr[i1] != arr[i2]) {
                return Integer.compare(arr[i2], arr[i1]);
            } else {
                return Integer.compare(i1, i2);
            }
        });

        FenwickTree ft = new FenwickTree(n);
        long[] pos = new long[n];
        for (int idx : indices) {
            // 查询索引<=idx的元素数量（已加入的都是值>=arr[idx]的）
            pos[idx] = ft.query(idx) + 1; // +1是因为要包含自己
            ft.update(idx, 1);
        }

        // 计算总和
        long result = 0;
        for (int i = 0; i < n; i++) {
            int a = arr[i];
            long prevSum = a > 0 ? sum_cnt[a - 1] : 0;
            result += prevSum + pos[i];
        }

        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] arr = {3, 1, 2};
        System.out.println(sol.solve(arr)); // 输出13，符合示例
    }
}

时间复杂度分析 #

• 统计频率、计算cnt和sum_cnt数组：O(n + maxA)，maxA≤1e4，可忽略不计
• 元素排序：O(n log n)
• 树状数组操作：每个元素对应一次查询和更新，总O(n log n)
• 最终求和：O(n)

整体时间复杂度为O(n log n)，完全适配题目中n≤1e5的约束。

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