algorithm - 求个位数数组的 N 个最大元素的总和

Question

<分区>

Answer 1

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

1. 遍历数组a并增加b[a[i]]其中 b是 10 个整数的零初始化数组。
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
}