leetcode：169. 多数元素

题目

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

进阶：

  • 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

示例：

  1. 输入：[3,2,3]
  2. 输出：3
  1. 输入：[2,2,1,1,1,2,2]
  2. 输出：2

解答 & 代码

如果数组中一个元素出现的次数大于 **⌊ n/2 ⌋** ，那么也就是说该数出现的次数 - 所有其它元素出现的次数 >0 。因此，使用 result 记录元素，使用 cnt 记录出现的次数，遍历数组：

  • 如果当前元素就是 element，令 cnt 加一
  • 否则，如果 cnt 为 0，则令 element 为当前元素，令 cnt = 1
  • 否则，令 cnt 减 1

那么，最后如果 cnt > 0，则 element 就是出现次数大于 ⌊ n/2 ⌋ 的元素；如果 cnt == 0，说明不存在出现次数大于 ⌊ n/2 ⌋ 的元素

  1. class Solution {
  2. public:
  3.     int majorityElement(vector<int>& nums) {
  4.         if(nums.size() == 0)
  5.             return -1;
  7.         int result = nums[0];
  8.         int cnt = 1;
  9.         for(int i = 1; i < nums.size(); ++i)
  10.         {
  11.             if(nums[i] == result)
  12.                 ++cnt;
  13.             else if(cnt == 0)
  14.             {
  15.                 result = nums[i];
  16.                 cnt = 1;
  17.             }
  18.             else
  19.                 --cnt;
  20.         }
  21.         return cnt > 0 ? result : -1;
  22.     }
  23. };

复杂度分析：设数组长为 N

  • 时间复杂度 O(N)：
  • 空间复杂度 O(1)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：12 ms, 在所有 C++ 提交中击败了 91.55% 的用户
  4. 内存消耗：19 MB, 在所有 C++ 提交中击败了 98.31% 的用户