求众数 II

问题描述

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例 1：
输入: [3,2,3]
输出: [3]

示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element-ii

思路

• 基本思路是用map（之前介绍过map内部实质是pair类型的）。
• 对于map中的每一项，只要它的second值大于n/3，就将其存入返回结果ret中。

题解

class Solution {
public:
    vector<int> majorityElement(vector<int> &nums) {
        map<int, int> table;
        vector<int> ret;
        int n = nums.size();
        if (n == 0) return ret;
        for (int i = 0; i < n; i++) {
            table[nums[i]]++;
        }
        for(auto each:table){
            if(each.second>n/3) ret.push_back(each.first);
        }
        return ret;
    }
};