Finding sum of N largest elements of array of single-digit values [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicate:

Retrieving the top 100 numbers from one hundred million of numbers

开发者_如何学Go

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:

1. Run through array a and increasе b[a[i]] where b is a zero initialized array of 10 integers.
2. 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.