find-majority-element-lcci

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

示例 1：

输入：[1,2,5,9,5,9,5,5,5]
输出：5

示例 2：

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

示例 3：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-majority-element-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

核心思想

假设存在元素a的数量超过一半,则将所有不同的元素相互抵消，剩余的那一个肯定是a.
如：

[2,2,1,1,1,2,2]
-> [2]

当不存在这样的元素时，也可能最后剩余的元素不符合条件，这时候就需要统计剩余元素的个数，然后判断是否超过总数的一半即可。
如：

[1,2,3]
-> [3]

Code

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int num = nums[0], count = 1, n = nums.size();
        for(int i =1; i<n; i++){
            if(count == 0){
                num = nums[i];
                count = 1;
            }else{
                if(nums[i] != num){
                    count --;
                }else count++;
            }
        }
        if(count == 0) return -1;
        else{
            count = 0;
            for(int nu: nums){
                if(nu == num) count++;
            }
            return count*2 >= n ? num:-1;
        }
    }
};