查找单位数值数组的N个最大元素的总和

Question

可能重复:
从一亿个数字中检索前100个数字

我有一个数组,其中包含0到9之间的正数,(数字可以重复).我想找到N个最大元素的总和

For example array =  5 1 2 4 and N=2
ans = 5+4 = 9

简单方法:排序数组并找到n个最大元素的总和.但我不想用它

Answer 1

最简单的O(n)解决方案如下:

1. 运行数组a并增加b[a[i]]其中b10个整数的零初始化数组.
2. 通过运行b从端部(9开始^日的位置),并且如果b[i]是低于N添加b[i] * i到你的答案,那么减少N通过b[i],否则如果b[i]大于或等于N添加N * i到应答,并通过回路.

编辑: 代码

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
}