Algorithm: given an array of numbers A, create an array B, where B [i] = sum (A [j]: A [j] <= A [i])
Example: A = [4, 1, 3, 2, 3, 3]. Then we get B = [16, 1, 12, 3, 12, 12].
Approach 1: For each i, just search for A and sum the numbers that are less than or equal to A [i]. Roughly speaking, this requires intersection through A n times, so it takes O (n ^ 2) time.
Approach 2: Sort A to get A 'and then just find the cumsum of A'. This requires transversion through A 'only once. So the total running time is just sorting, O (n log n).
However, this does not work when there are connections. In the above example we get A '= [1, 2, 3, 3, 3, 6], so cumsum (A') = [1, 3, 6, 9, 12, 16] which is not the same as B (sorted).
Is there a way to fix this so that it still runs in O (n log n)?
source share
One way to do this with modern languages is to use dictionnary:
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)
When constructing a dictionnary, the last value found replaces the existing one, so at least it is good enough. This gives:
[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]
source share
Ok if you allow O(n log n)
Then here is a very simple approach to achieve it:
- Copy A to 'and sort A', O (n lg n)
- Calculate prefix sum of A ', store them in S, O (n)
- Loop through A for each element of A_i, binary search largest index
j
in 'such that A' [j]> = A_i, Ans [i] = S [J]
Ans is the array you want
Below is a sample C ++ code illustrating the idea
#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; }
source share
A better approach would be to sort A to A '= [1, 3, 6, 9, 12, 16], then find the total sum of the integers, and instead of cumsum, iterate over the array as shown below
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]; } }
source share
I have an easy approach to this at o (nlogn).
- sort the array in relation to their value in ascending order. When sorting the index of an element, the element should be treated. For sorting in java you can use the built-in function
java.util.Arrays.sort(input, new java.util.Comparator<int[]>() { public int compare(int[] a, int[] b) { return Double.compare(a[1], b[1]); } });
- create a temporary array that will contain the response.
- calculate the sum of the entire element in the sorted array.
- move a sorted array from back to front.
- maintain counting for adjacent similar number.
- when you get a different value from next value update sum with count * nextvalue sum.
- save the sum at the index of the current value;
Here is my java code
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]+" "); } }
source share