整数列表与区间生成新列表的高效求和算法优化求助

问题描述 #

给定大小为n的整数列表，以及包含m个区间的列表（每个区间表示原列表的起止索引），需完成以下操作：

1. 生成新列表 #

遍历所有区间，将每个区间内的原列表元素依次追加到新列表中。示例如下：

n=6, list = [1, 2, 3, 2, 4, 5]
m=4, ranges = [[0, 1], [3, 4], [0, 0], [3, 4]]

生成过程：

i=0时，区间[0,1]，取list[0]到list[1]，新列表为[1,2]
i=1时，区间[3,4]，取list[3]到list[4]，新列表为[1,2,2,4]
i=2时，区间[0,0]，取list[0]，新列表为[1,2,2,4,1]
i=3时，区间[3,4]，取list[3]到list[4]，新列表为[1,2,2,4,1,2,4]

2. 计算结果 #

初始化result=0，遍历原列表索引i从0到n-1：

• 若i属于任一区间，向result加0；
• 若i不属于任何区间，统计新列表中值小于list[i]的元素数量并累加到result中。

示例计算过程：

初始化result = 0
i=0：属于区间[0,1]、[0,0]，加0，result=0
i=1：属于区间[0,1]，加0，result=0
i=2：不属于任何区间，统计新列表中小于3的元素数量为5，result=5
i=3：属于区间[3,4]，加0，result=5
i=4：属于区间[3,4]，加0，result=5
i=5：不属于任何区间，统计新列表中小于5的元素数量为7，result=12

现有代码的瓶颈 #

原代码通过遍历每个区间的所有元素来统计频率，时间复杂度为O(m*k)（k为区间平均长度），当区间数量多、范围大时，效率极低。尝试合并区间会丢失索引被重复覆盖的次数，导致频率统计错误。

优化方案 #

核心思路 #

1. 用差分数组统计索引覆盖次数：快速计算每个原列表索引被多少个区间包含（即对应元素在新列表中的出现次数），时间复杂度O(m + n)。
2. 构建排序元素+前缀和数组：将元素按值排序，配合前缀和数组实现O(logS)复杂度的查询（S为不同元素的数量），快速得到小于目标值的总元素数。

优化后的代码 #

import java.util.*;

public class Main {

    public static long solution(List<Integer> list, List<List<Integer>> ranges) {
        int n = list.size();
        // 1. 用差分数组计算每个索引的覆盖次数
        int[] countDiff = new int[n + 1];
        for (List<Integer> range : ranges) {
            int start = range.get(0);
            int end = range.get(1);
            countDiff[start]++;
            if (end + 1 < n) {
                countDiff[end + 1]--;
            }
        }

        // 计算每个索引的实际覆盖次数，同时标记是否属于任何区间（覆盖次数>0）
        boolean[] inRange = new boolean[n];
        Map<Integer, Long> valueTotalCount = new HashMap<>();
        int currentCount = 0;
        for (int i = 0; i < n; i++) {
            currentCount += countDiff[i];
            inRange[i] = currentCount > 0;
            if (currentCount > 0) {
                // 累计该元素的总出现次数
                valueTotalCount.put(list.get(i), 
                    valueTotalCount.getOrDefault(list.get(i), 0L) + currentCount);
            }
        }

        // 2. 构建排序的元素列表和前缀和数组
        List<Map.Entry<Integer, Long>> sortedEntries = new ArrayList<>(valueTotalCount.entrySet());
        sortedEntries.sort(Map.Entry.comparingByKey());
        int size = sortedEntries.size();
        long[] prefixSum = new long[size + 1];
        for (int i = 0; i < size; i++) {
            prefixSum[i + 1] = prefixSum[i] + sortedEntries.get(i).getValue();
        }

        long result = 0;
        // 遍历原列表，计算结果
        for (int i = 0; i < n; i++) {
            if (!inRange[i]) {
                int target = list.get(i);
                // 二分查找第一个大于等于target的元素位置
                int left = 0, right = size;
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (sortedEntries.get(mid).getKey() >= target) {
                        right = mid;
                    } else {
                        left = mid + 1;
                    }
                }
                result += prefixSum[left];
            }
        }

        return result;
    }
    
    static void case1() {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
        List<List<Integer>> ranges = Arrays.asList(
                Arrays.asList(0, 1),
                Arrays.asList(0, 2),
                Arrays.asList(1, 2)
        );
        System.out.println(solution(list, ranges)); // Output: 14
    }
    static void case2() {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
        List<List<Integer>> ranges = Arrays.asList(
                Arrays.asList(1, 2),
                Arrays.asList(1, 1),
                Arrays.asList(2, 2),
                Arrays.asList(3, 3),
                Arrays.asList(4, 4)
        );
        System.out.println(solution(list, ranges)); // Output: 0
    }
    
    static void case3() {
        List<Integer> list = Arrays.asList(1, 2, 3, 2, 4, 5);
        List<List<Integer>> ranges = Arrays.asList(
                Arrays.asList(0,1),
                Arrays.asList(3,4),
                Arrays.asList(0,0),
                Arrays.asList(3,4)
        );
        System.out.println(solution(list, ranges)); // Output: 12
    }

    public static void main(String[] args) {
        case1();
        case2();
        case3();
    }
}

复杂度分析 #

• 差分数组处理：O(m + n)
• 元素排序：O(S log S)（S为原列表中不同元素的数量，S ≤ n）
• 查询阶段：O(n log S)
  整体时间复杂度为O(m + n + S log S + n log S)，远优于原代码的O(m*k)，适合处理大规模输入。

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