Leetcode题库169.多数元素

文章目录

• 思路
• 代码

思路

设多数元素为x，数组中x的数量 > n/2
设置一个ret，保存当前活着的元素
设置一个计数器num，记录当前ret的数量

设置ret为数组第1个元素
num为1

遍历数组
若num[i]的值=ret，则num+1(相同元素则叠加)
若num[i]的值!=ret，否则num-1(不同元素则抵消)
当num=0时，则重置num和ret(num为0说明之前最多的元素已经被抵消完了)

因为x的数量 > n/2，所以最后必定有x未被抵消，ret中保存的就是x

代码

int majorityElement(int* nums, int numsSize){
    int num = 1,ret = nums[0];
    for(int i=1;i<numsSize;i++){
        num += (ret==nums[i])-(ret!=nums[i]);
        if(num==0) {num = 1;ret = nums[i];}
    }
    return ret;
}