摩尔投票算法

摩尔投票算法

摩尔投票算法
给你一个长度为 n 的数组，其中只有一个数字出现了大于 n/2 次，问如何快速找到这个数字。

第一种写法

public int find(int[] nums) {
    int count = 1;
    int result = nums[0];
    for (int i = 1; i < nums.length; i++) {
        count = result == nums[i] ? ++count : --count;
        if (count == 0) {
            result = nums[i + 1];
        }
    }
    return result;
}

第二种写法

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

摩尔投票算法
摩尔投票算法是用于找出数组中出现次数超过n/2的元素，其核心思想在于遍历过程中不同元素之间两两抵消，由于一个数组中，出现次数超过n/2最多只有一个，那么遍历结束时，未被抵消掉的即是出现次数超过n/2的元素。

数学思想
众数一定比其他所有的数加起来的数量要多，就算是众数与其他每一个数相抵消，最后剩下来的也是众数。

扑克牌抽象算法

假如有9张扑克牌（ 8，8，8，7，8，4，2，8，2），依次抓牌，手里抓两张牌，比较两张牌是否一样。不一样就把两张牌放下，一样就放手里继续抓牌。手里没有牌继续抓两张牌比较。手里有牌继续抓一张牌比较如果和手里牌相同就留下，不同就拿出两张不同的牌。你会发现手里最后剩余的就是 8。