一、题目

数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

点击查看原题
难度级别： 简单

二、思路

1）投票+验证

如果一个数出现的次数大于这个数组长度的一半，使用投票算法可以得到这个数：

用候选人变量记录选中的元素和该元素出现的次数，在遍历的时候，如果出现非候选人变量，则候选人变量出现次数减一，当减到0，就更换候选人变量的值为当前遍历到的数组元素，由于主要元素出现次数大于数组长度的一半，一定可以获得主要元素（如果存在的话）

考虑到没有主要元素的情况，需要遍历一遍数组，将候选人变量出现的次数记录一下，判断是否主要元素

三、代码

1）投票+验证

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

时间复杂度为O(N)，空间复杂度为 O(1)