问题描述:

Possible Duplicate:Retrieving the top 100 numbers from one hundred million of numbers

I have a array which consists positive number between 0 to 9,(digit can repeat). I want to find sum of N largest elements

`For example array = 5 1 2 4 and N=2`

ans = 5+4 = 9

Simple approach: sort array and find sum of n largest elements. But i dont want to use it

The simplest O(n) solution is the following:

- Run through array
`a`

and increasе`b[a[i]]`

where`b`

is a zero initialized array of 10 integers. - Run through
`b`

starting from the end (9^{th}position) and if`b[i]`

is lower than`N`

add`b[i] * i`

to your answer, then decrease`N`

by`b[i]`

, otherwise if`b[i]`

is greater or equal to`N`

add`N * i`

to the answer and over the loop.

**Edit:** *code*

```
vector<int> b(10, 0);
for(int i = 0; i < a.size(); ++i) {
b[a[i]]++;
}
int sum = 0;
for(int i = 9; i >= 0; --i) {
if(b[i] < n) {
sum += b[i] * i;
n -= b[i];
} else {
sum += n * i;
n = 0;
break;
}
}
if(n != 0) {
// no enough element in the array
}
```

insert all into a heap, and then delete (and sum) N elements.

complexity: `O(n+Nlogn)`

, because creating a heap is O(n), and each delete is O(logn), and you iterate over delete N times. total: O(n+Nlogn) [where n is the number of elements in your array].

**EDIT**: I missed it at first, but all your numbers are digits. so the simplest solution will be using radix sort or bucket sort and then sum the N biggest elements. solution is O(n).

I am a bit slow today, should code faster hehe ;-)

There are multiple answers already but I want to share my pseudo-code with you anyway, hope it helps!

```
public class LargestSumAlgorithm
{
private ArrayList arValues;
public void AddValueToArray(int p_iValue)
{
arValues.Add(p_iValue);
}
public int ComputeMaxSum(int p_iNumOfElementsToCompute)
{
// check if there are n elements in the array
int iNumOfItemsInArray = arValues.Size;
int iComputedValue = 0;
if(iNumOfItemsInArray >= p_iNumOfElementsToCompute)
{
// order the ArrayList ascending - largest values first
arValues.Sort(SortingEnum.Ascending);
// iterate over the p_iNumOfElementsToCompute in a zero index based ArrayList
for(int iPositionInValueArray = 0; iPositionInValueArray < p_iNumOfElementsToCompute); iPositionInValueArray++)
{
iComputedValue += arValues[i];
}
}
else
{
throw new ArgumentOutOfRangeException;
}
return iComputedValue;
}
public LargestSumAlgorithm()
{
arValues = new ArrayList();
}
}
public class Example
{
LargestNumAlgorithm theAlgorithm = new LargestSumAlgorithm();
theAlgorithm.AddValueToArray(1);
theAlgorithm.AddValueToArray(2);
theAlgorithm.AddValueToArray(3);
theAlgorithm.AddValueToArray(4);
theAlgorithm.AddValueToArray(5);
int iResult = theAlgorithm.ComputeMaxSum(3);
}
```

If you are using C++, use std::nth_element() to partition the array into two sets, one of them containing the N largest elements (unordered). Selection algo runs in O(n) time.