题解 | #牛的品种排序III# 计数

知识点

计数

思路

对k个数字计数，然后一次对原数组赋值。时间复杂度为

AC code （C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型vector 
     * @param k int整型 
     * @return int整型vector
     */
    vector<int> sortCowsIII(vector<int>& cows, int k) {
        vector<int> cnt(k);
        for (auto x : cows) {
            cnt[x] += 1;
        }
        for (int i = 0, j = 0; i < k; i ++) {
            while (cnt[i] --) {
                cows[j ++] = i;
            }
        }
        return cows;
    }
};