算法：给定一个数字数组A，创建一个数组B，其中B[i]= sum(A[j]: A[j] <= A[i])

Question

例子：A = [4, 1, 3, 2, 3, 3]。那么我们将得到B = [16, 1, 12, 3, 12, 12]。

方法1：对于每个i，只需搜索A并总结小于或等于A[i]的数字。粗略地说，这需要遍历A n次，因此它将花费O(n^2)时间。

方法2：将A排序以获得A'，然后只需找到A'的累加和。这仅需要遍历一次A'。因此，总运行时间仅为排序的O(n log n)。

但是，当存在并列时，这种方法不起作用。对于上面的例子，我们得到A' = [1, 2, 3, 3, 3, 6]，因此cumsum(A') = [1, 3, 6, 9, 12, 16]，这与B（排序后）不同。

有没有一种方法可以修复这个问题，使其仍在O(n log n)中运行？

- tangleduniform8

Answer 1

使用现代语言实现这一点的一种方法是使用字典：

A=random_integers(1,10,10)
SA=sorted(A) #O(n log n)
CSA=cumsum(SA)  #O(n)
I=dict(zip(SA,CSA)) #O(n)
B=[I[x] for x in A] #O(n)

在构建字典时，最后一个值会替换现有的值，以便至少符合正确的值。这样就得到了：

[7 5 4 1 4 2 6 7 8 2]
[1 2 2 4 4 5 6 7 7 8]
[1 3 5 9 13 18 24 31 38 46]
{1:1, 2:5, 4:13, 5:18, 6:24, 7:38, 8:46}
[38 18 13 1 13 5 24 38 46 5] 

- B. M.

---

良好地使用计数字典。 - Ami Tavory

Answer 2

如果您允许 O(n log n)，那么这里有一种非常简单的方法来实现：

1. 将A复制到A'并对A'进行排序，O(n lg n)
2. 计算A'的前缀和，将它们存储在S中，O(n)
3. 循环遍历A，对于每个元素A_i，在A'中二分查找最大的索引j，使得A'[j] >= A_i，Ans[i] = S[j]

Ans是您想要的数组

下面是一个示例C++代码，说明了这个思路

#include<bits/stdc++.h>
using namespace std;

int A[6] = {4, 1, 3, 2, 3, 3}, B[6], SUM[6] = {0}, ANS[6];

int main(){
 for(int i=0; i<6; i++) B[i] = A[i];
 sort(B, B+6);
 for(int i=0; i<6; i++) SUM[i] = (i? SUM[i-1]:0) + B[i];
 
 for(int i=0; i<6;i++){
  int j = upper_bound(B,B+6, A[i]) - B;
  ANS[i] = SUM[j-1];
  printf("%d ", ANS[i]);
 }
 puts("");

 return 0;
}

- shole

Answer 3

更好的方法是先将A排序为A'=[1, 3, 6, 9, 12, 16]，然后找出整数的总和，而不是使用cumsum函数，可以像下面这样遍历数组：

B[A.length-1] = sum;
for(int i=A.length-2; i=0; i++){
    if(A[i]!=A[i+1]){
        B[i] = sum - B[i+1];
    }
    else{
        B[i] = B[i+1];
    }
}

- Manu

Answer 4

在排序的方法中，在存储结果之前，找到所有具有相同值的元素（现在都是连续的，因此这与您已经执行的遍历相同），并一起处理：计算总和（对于所有元素都相同），然后为每个元素记录（相同的）结果。

- moreON

Answer 5

我有一个简单的方法可以在O(nlogn)时间内完成。

• 按照元素值的大小顺序对数组进行排序。在排序时，元素的索引应该与元素一起排序。在Java中，您可以使用内置函数进行排序。

  java.util.Arrays.sort(input, new java.util.Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return Double.compare(a[1], b[1]);
            }
        });

创建一个临时数组，其中将包含答案。 计算已排序数组中所有元素的总和。 从后往前遍历已排序数组。 维护连续相似数字的计数。 当从下一个值获得不同的值时，使用sum-count*nextvalue更新sum。 将该和存储在当前值的索引处; 这是我的Java代码

class Solution
{
 public static void main (String[] args) throws java.lang.Exception
 {
  int[][] input={{0,4}, {1,1}, {2,3}, {3,2}, {4,3}, {5,3
  
          //sort one column with respect to other column in 2d array
    java.util.Arrays.sort(input, new java.util.Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return Double.compare(a[1], b[1]);
            }
           });
        
           int[] temp=new int[6];   //Answer array
           int sum=0;
           
           for(int i=0;i<6;i++){
               sum=sum+input[i][1];
           }
           
           int count=1;
           temp[input[5][0]]=sum;
           
           for(int i=4;i>=0;i--){
               if(input[i][1]==input[i+1][1]){
                   count++;
                   temp[input[i][0]]=sum;
               }
               else{
                   sum=sum-(count*input[i+1][1]);
                   temp[input[i][0]]=sum;
                   count=1;
               }
           }
           
           for(int i=0;i<6;i++)
              System.out.print(temp[i]+" ");
 }
}

- nikhil jain