169. 多数元素

一、题目描述

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋的元素。

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

二、解题思路

投票法，相同值 +1，不同值 -1。

因为有一半元素以上是同一个值，所以最终投票结果肯定是超过半数的那个元素。

三、复杂度分析

• 时间 O(n)
• 空间 O(1)

四、参考代码

/**
 * 寻找出现次数大于一半的元素
 *
 * @param nums 数组
 * @return 大于一半数量的元素
 */
private int majorityElement(int[] nums) {
    // 投票法，相同值+1，不同值-1
    // 因为有一半元素以上是同一个值，所以最终投票结果肯定是超过半数的那个元素
    int x = nums[0];
    int count = 1;
    for (int i = 1; i < nums.length; i++) {
        if (count == 0) {
            x = nums[i];
            count++;
            continue;
        }
        if (x == nums[i]) {
            count++;
        } else {
            count--;
        }
    }
    return x;
}