leetCode 169 多数元素

题目描述：

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例输入输出：

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

思路：

摩尔投票

  • 因为多数元素出现次数>n/2，所以可以利用计数方法，一个数出现+1，另一个数出现-1，当此数计数为0，则用另外的数替代

  • 参数：

    • cnum 标志需要被计数的数

  • 流程：

    • 初始化cnum与count
    • 遍历nums，如果num[i]与cnum相同，count自增，否则count自减
    • 如果count == 0，将nums[i+1]赋值给cnum，这样遍历下一个元素时，count会变成1.

  • 复杂度分析：

    • 时间复杂度：O（n）
    • 空间复杂度：O（1）

  • 代码：

  • class Solution {
  public int majorityElement(int[] nums) {
      int cnum = nums[0];
      int count = 1;
      for(int i = 1; i < nums.length; i++){
          if(cnum == nums[i]) count++;
          else count --;
          if(count == 0){
              cnum = nums[i+1];
          }
      }
      return cnum;
  }
}