【leetcode C语言实现】剑指 Offer 39.数组中出

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制：

1 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof

解题思路

由于题目已明确给定的数组中总是存在多数元素，所有可以利用这个特点，采用摩尔投票法，正负相抵后最终剩下的即为数组中出现次数超过一半的数字，也即众数。

代码

int majorityElement(int* nums, int numsSize){

    int counter = 0, major = 0;

    for (int i = 0; i < numsSize; i++)
    {
        if (counter == 0)
            major = nums[i];
        if(nums[i] == major)
            counter += 1;
        else
            counter -= 1;
    }
    return major;
}

执行结果