多数元素LeetCode169

投票法 O(n) time, O(1) space

  • 一个候选人

    1. class Solution {
    2. public:
    3.   int majorityElement(vector<int>& nums) {
    4.       int candidate, vote = 0;
    5.       for (auto num: nums) {
    6.           if (vote == 0) candidate = num;
    8.           if (candidate == num) vote ++;
    9.           else vote --;
    10.       }
    11.       return candidate;
    12.   }
    13. };

    求中位数 O(n) time, O(1) space

    1. class Solution {
    2. public:
    3.   int majorityElement(vector<int>& nums) {
    4.       nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
    5.       return nums[nums.size() / 2];
    6.   }
    7. };

    求众数II LeetCode229

    投票法 O(n) time, O(1) space

  • 2个候选人

    1. class Solution {
    2. public:
    3.   vector<int> majorityElement(vector<int>& nums) {
    4.       int candy1 = -2e9, candy2 = -2e9;
    5.       int vote1 = 0, vote2 = 0;
    6.       for (auto num: nums) {
    7.           if (candy1 == num) {
    8.               vote1 ++;
    9.           } else if (candy2 == num) {
    10.               vote2 ++;
    11.           } else{
    12.               if (vote1 == 0) {
    13.                   candy1 = num;
    14.                   vote1 ++;
    15.               } else if (vote2 == 0) {
    16.                   candy2 = num;
    17.                   vote2 ++;
    18.               } else {
    19.                   vote1 --;
    20.                   vote2 --;
    21.               }
    22.           }
    23.       }
    24.       vote1 = 0, vote2 = 0;
    25.       for (auto num: nums) {
    26.           if (num == candy1) vote1 ++;
    27.           if (num == candy2) vote2 ++;
    28.       }
    29.       vector<int> ans;
    30.       if (vote1 > nums.size() / 3) ans.push_back(candy1);
    31.       if (vote2 > nums.size() / 3) ans.push_back(candy2);
    32.       return ans;
    33.   }
    34. };

    求数组频率出现最高的k个数

    计数排序思想，O(n) time, O(n) space

    class Solution {
public:
  vector<int> topKFrequent(vector<int>& nums, int k) {
      unordered_map<int, int> cnt;
      // caculate count of each num
      for (auto num: nums) {
          cnt[num] ++;
      }

      vector<int> f(nums.size() + 1);
      for (auto [num, c]: cnt) {
          f[c] ++;
      }

      int t_min = f.size() - 1;
      for (int i = f.size() - 1; i >= 0; i --) {
          k -= f[i];
          t_min = i;
          if (k <= 0) {
              break;
          }
      }

      vector<int> ans;
      for (auto [num, c]: cnt) {
          if (c >= t_min) {
              ans.push_back(num);
          }
      }
      return ans;
  }
};