【Check 84】2024-05-28 - 169. 多数元素

[larscheng]

169. 多数元素

[larscheng]

思路

投票大法，

• 首个元素为待选值，他的票数为1，遇到相同的值，票数+1，遇到不同的值，票数-1，如果-1后票数为0，则更换待选值,重置票数为1
• 原理：众数个数大于n/2，其他数个数必定小于n/2，众数个数和-其他数个数和>=1

• O(n)/O(1)

  代码

  
  
   */
  public int majorityElement(int[] nums) {
      int result = nums[0];
      int count =1;
      for (int i = 1; i < nums.length; i++) {
          if (result==nums[i]){
              ++count;
          } else if (--count==0) {
              result = nums[i];
              count=1;
          }
      }
      return result;
  }

### 复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(1)