给定一个列表和范围，在更短的时间内根据新列表求和

Question

给定一个大小为

n

的整数列表，以及

m

范围列表，其中每个范围表示输入列表的开始和结束索引。

首先使用这个范围创建一个新列表，例如：

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

要创建一个新列表，我们循环遍历范围，即从

i=0 to m

开始，并在这些索引处选择项目：

for i=0, [0,1], pick items from list[0] to list[1], and append to newList, so newList = [1,2]
for i=1, [3,4], pick items from list[3] to list[4], and append to newList, so newList = [1,2,2,4]
for i=2, [0,0], pick items from list[0] to list[0], so newList = [1,2,2,4,1]
for i=3, pick items list[3], list[4] so newList = [1,2,2,4,1,2,4]

接下来循环 i 到 0 到 n，如果索引 i 属于上述任何范围，则在结果中添加 0，如果它不属于任何范围，则计算 newList 中有多少项的值小于列表[i]

initialize result = 0
for i=0, it is part of range [0,1],[0,0] so adds 0 to result
for i=1, it is part of range [0,1] so adds 0 to result
for i=2, it is not part of any ranges so count how many items are there in newList [1,2,2,4,1,2,4], whose values are less than list[2] = 3, we get [1,2,2,1,2], so 5
for i=3, it is part of range [3,4] so adds 0 to result
for i=4, it is part of range [3,4] so adds 0 to result
for i=5, it is not part of any ranges so count how many items are there in newList [1,2,2,4,1,2,4], whose values are less than list[5] = 5, we get [1,2,2,4,1,2,4], so 7

Result = 0 + 0 + 5 + 0 + 0 + 7 = 12

我已经为此实现了代码，但需要更多时间来处理。

这是我的代码：

import java.util.*;

public class Main {

    public static long solution(List<Integer> list, List<List<Integer>> ranges) {
        // Create a set to keep track of all indices that contribute to new list
        Set<Integer> contributingIndices = new HashSet<>();
        
        // TreeMap to maintain the frequency of elements in the new list
        TreeMap<Integer, Integer> freqMap = new TreeMap<>();
        
        // Populate the frequency map and contributing indices
        for (List<Integer> range : ranges) {
            int start = range.get(0);
            int end = range.get(1);
            for (int i = start; i <= end; i++) {
                freqMap.put(list.get(i), freqMap.getOrDefault(list.get(i), 0) + 1);
                contributingIndices.add(i);
            }
        }

        long totalBeauty = 0;

        for (int i = 0; i < list.size(); i++) {
            if (!contributingIndices.contains(i)) {
                // Calculate the number of elements in map that are smaller than list[i]
                totalBeauty += freqMap.headMap(list.get(i), false)
                                        .values()
                                        .stream()
                                        .mapToInt(Integer::intValue)
                                        .sum();
            }
        }
    
        return totalBeauty;
    }
    
    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();
    }
}

为了缩短时间，我尝试合并范围，然后开始创建 freqMap，但它在合并间隔时给出了错误的频率，因此我们得到了错误的频率计数。

我正在寻找更好的解决方案，需要更少的时间复杂度

Answer 1

不确定更快，你需要测量它，但更简单：

    public static long solution(List<Integer> list, List<List<Integer>> ranges) {
        // Create a set to keep track of all indices that contribute to new list
        Set<Integer> contributingIndices =
                IntStream.range(0, list.size())
                        .boxed()
                        .collect(Collectors.toSet());

        // TreeMap to maintain the frequency of elements in the new list
        TreeMap<Integer, Integer> freqMap = new TreeMap<>();

        // Populate the frequency map and contributing indices
        for (List<Integer> range : ranges) {
            int start = range.get(0);
            int end = range.get(1);
            for (int i = start; i <= end; i++) {
                freqMap.merge(list.get(i), 1, Integer::sum);
                contributingIndices.remove(i);
            }
        }

        // Calculate the number of elements in map that are smaller than list[i]
        return contributingIndices.stream().flatMapToInt(i ->
                        freqMap.headMap(list.get(i), false)
                                .values()
                                .stream()
                                .mapToInt(Integer::intValue))
                .sum();
    }