LeetCode 每日一题 [58] 数组中出现次数超过一半的数

LeetCode 数组中出现次数超过一半的数字 [简单]

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

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

示例 1:

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

限制：

1 <= 数组长度 <= 50000

题目分析

方法1

暴力在手，天下我有

方法2

摩尔投票法 核心理念为“正负相抵” 因为众数的个数超过数组长度的一半

解法3

数组排序法，因为众数超过数组的一般，所以数组的中间值一定是目标值

解法4

使用hashmap进行统计

代码实现 仅仅实现 摩尔投票法

public class MajorityElement {
    public static void main(String[] args) {
        int[] target = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        System.out.println(majorityElement(target));
        System.out.println(majorityElement1(target));
    }

    public static int majorityElement1(int[] nums) {
        int target = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (target == nums[i]) {
                count++;
            } else {
                count--;
            }
            if (count == 0) {
                target = nums[i];
                count = 1;
            }
        }
        return target;
    }

    public static int majorityElement(int[] nums) {
        int x = 0, votes = 0;
        for (int num : nums) {
            if (votes == 0) {
                x = num;
            }
            votes += num == x ? 1 : -1;
        }
        return x;
    }
}