3

考虑一个数组（基于 0 的索引）我必须找到所有可能 range[i,n] 的不同元素的总和，其中 0< i < n

例子：

arr={1,2,1,3}

sum_range[0,3]={1,2,3}=6
sum_range[1,3]={1,2,3}=6
sum_range[2,3]={1,3}=4
sum_range[3,3]={3}=3

O(n^2) 解决方案是一种可能的解决方案，虽然我找不到好的教程，但我已经阅读了持久段树也可以做到这一点。

它可以在少于 O(N^2) 的时间内解决吗？

如果有人指向持久段树，请解释或提供一些好的链接？

4

3 回答 3

5

这可以通过简单的动态规划算法在 O(n) 中完成。

从数组的后面开始，使用一个基于散列的容器来存储你已经遇到的数字。最后一个元素的值，即sum_range[n-1]设置为arr[n-1]。之后，sum_range[i]应按如下方式计算 的值：

  • 如果arr[i]不在所见数字的集合中，sum_range[i] = sum_range[i+1]+arr[i]
  • 否则，sum_range[i] = sum_range[i+1]

由于检查散列容器的值的成本是 O(1)，并且将项目添加到散列容器的成本对 n 个项目分摊 O(1)，因此该算法的总成本是 O(n)。

与使用 O(1) 空间的 O(n 2 ) 算法相比，该算法为散列容器使用了额外的 O(n) 空间。

于 2016-01-01T16:50:23.613 回答
0

对数组进行切片 (O(n))，然后使用集合并将值添加到集合中。

在 python3.x 代码中，在注释后编辑：

array = [1, 2, 1, 3, 5]
range_sum = 0
total_sum = 0
valueset = set ()
for val in reversed(array):
    if val not in valueset :
        valueset.add (val)
        range_sum += val
    total_sum += range_sum

print (total_sum)
于 2016-01-01T16:56:16.283 回答
0

有多种方法可以解决这个问题。

  1. 对数组进行排序Arrays.sort();

  2. 使用集合

    long sumOfDistinct(long arr[], int N)
{
     int size = arr.length;
     HashSet<Long> unique = new HashSet<Long>(); 
     long sum = 0;
     for(int i=0;i<size;i++){
             if(!unique.contains(arr[i])){
                 sum = sum + arr[i];
                 unique.add(arr[i]);
             }
     }

     return sum;
 }
于 2022-02-13T20:00:59.370 回答