题解 | #牛的体重统计#

知识点

哈希表

思路说明

利用哈希表统计不同体重的牛的个数; 遍历哈希表找到众数

时间复杂度

遍历一遍数组的时间复杂度为 $O(n)$

unordered_map插入的时间复杂度为 $O(n)$

遍历哈希表的时间复杂度为 $O(n)$

综合时间复杂度为 $O(n)$

AC code (C++)

#include <unordered_map>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weightsA int整型vector 
     * @param weightsB int整型vector 
     * @return int整型
     */
    int findMode(vector<int>& weightsA, vector<int>& weightsB) {
        // write code here
        unordered_map<int, int> cnt;
        for (auto x : weightsA) cnt[x] += 1;
        for (auto x : weightsB) cnt[x] += 1;
        int res = -1, mx = -1;
        for (auto [k, v] : cnt) {
            if (v > mx or (v == mx and k > res)) {
                mx = v;
                res = k;
            }
        }
        return res;
    }
};