algo-aha

出现次数>N/2的数

• https://leetcode.com/problems/majority-element/

用碰撞抵消法找出一数，最后再数一遍验证是不是。比如从{2,3,1}中找到1，还要验证1是不是。若已知众数存在就不用验证。

已知众数存在时，也可用快速划分法直接找中位数。

int majorityElement(vector<int>& nums) {
    int cand = INT_MIN;
    int cnt = 0;
    for (int num : nums) {
        if (num == cand) {
            cnt++;
        } else if (cnt == 0) {
            cand = num;
            cnt++;
        } else {
            cnt--;
        }
    }
    return cand;
}

所有出现次数>N/k的数

• https://leetcode.com/problems/majority-element-ii/

vector<int> majorityElement(vector<int>& nums) {
    // 一般化，找出现次数>N/k的元素
    // 用个map统计各候选的出现次数，当map.size()==k时删掉k个不同元素，
    // 最后剩下的为候选
    unordered_map<int, int> cnt;
    for (auto num : nums) {
        cnt[num]++;
        if (cnt.size() == 3) {
            auto it = cnt.begin();
            while (it != cnt.end()) {
                it->second--;
                if (it->second == 0) {
                    it = cnt.erase(it);
                } else {
                    it++;
                }
            }
        }
    }
    // 需要验证候选的出现次数
    for (auto &e : cnt) {
        e.second = 0; // 给候选重新计数
    }
    for (auto num : nums) {
        if (cnt.count(num)) cnt[num]++;
    }
    vector<int> ans;
    for (auto &e : cnt) {
        if (e.second > nums.size() / 3) {
            ans.push_back(e.first);
        }
    }
    return ans;
}

bst中找众数

• https://leetcode.com/problems/find-mode-in-binary-search-tree/

vector<int> findMode(TreeNode* root) {
    // bst中找众数，中序遍历找连续出现最多的数
    vector<int> ans;
    int prev = INT_MIN;
    int count = 0, maxCount = INT_MIN;
    inorder(root, prev, count, maxCount, ans);
    return ans;
}

void inorder(TreeNode *root, int &prev, int &count, int &maxCount, vector<int> &ans) {
    if (!root) return;
    inorder(root->left, prev, count, maxCount, ans);

    if (root->val != prev) count = 1;
    else count++;
    if (count > maxCount) {
        maxCount = count;
        ans = { root->val };
    } else if (count == maxCount) {
        ans.push_back(root->val);
    }

    prev = root->val;
    inorder(root->right, prev, count, maxCount, ans);
}