169. 多数元素

Powered by:NEFU AB-IN

Link

169. 多数元素

• 题意

  给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
  你可以假设数组是非空的，并且给定的数组总是存在多数元素。

• 思路

  1. 数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数。
  2. 摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N) 和 O(1)，为本题的最佳解法。

• 代码

  #define int long long
  #undef int
  
  #define SZ(X) ((int)(X).size())
  
  class Solution {
  public:
      int majorityElement(vector<int>& nums) {
          sort(nums.begin(), nums.end());
          return nums[nums.size() / 2];
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12

  class Solution {
  public:
      int majorityElement(vector<int>& nums) {
          int x = 0, votes = 0, count = 0;
          for (int num : nums){
              if (votes == 0) x = num;
              votes += num == x ? 1 : -1;
          }
          // 验证 x 是否为众数
          for (int num : nums)
              if (num == x) count++;
          return count > nums.size() / 2 ? x : 0; // 当无众数时返回 0
      }
  };
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15