leetcode-面试题 17.10 主要元素(投票算法)

面试题 17.10. 主要元素 - 力扣（LeetCode） (leetcode-cn.com)

题意

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

思路

多数投票算法

算法原理为每次寻找不同的两个数字，将其从数组中删去，那么最后一定能得到数组中出现次数超过一半的数字

实现细节为：

• 记录当前数字X出现的次数num，即假定当前数字为出现次数大于一半的数字

• 如果下一个数字和当前数字相同则num加一，否则num减一

• 如果num为0，更新数字X

• 最后得到的X即为出现次数大于一半的数

代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ans;
        int cnt=0;
        for(auto &x: nums){
            if(cnt == 0){
                ans = x;
            }if(x == ans) cnt++;
            else if(x != ans) cnt--;
         }
        cnt=0;
        cout<<ans<<endl;
        for(auto &x: nums){
            if(x == ans)
                cnt++;
        }if(cnt <= nums.size()/2) ans=-1;
        return ans;
    }
};