摩尔投票

作者：喝七喜
链接：https://www.zhihu.com/question/49973163/answer/235921864
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

摩尔投票算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

为了方便理解举一个示例输入：{1,2,1,3,1,1,2,1,5}

• 从第一个数字1开始，我们想要把它和一个不是1的数字一起从数组里抵消掉，但是目前我们只扫描了一个1，所以暂时无法抵消它，把它加入到array，array变成了{1}，

• result由于没有抵消任何元素所以还是原数组{1,2,1,3,1,1,2,1,5}。然后继续扫描第二个数，是2，我们可以把它和一个不是2的数字抵消掉了，因为我们之前扫描到一个1，所以array变成了{},result变成了{1,3,1,1,2,1,5}

• 继续扫描第三个数1，无法抵消，于是array变成了{1},result还是{1,3,1,1,2,1,5};

• 接下来扫描到3,可以将3和array数组里面的1抵消,于是array变成了{},result变成了{1,1,2,1,5}接下来扫描到1，此时array为空，所以无法抵消这个1，array变成了{1},result还是{1,1,2,1,5}

• 接下来扫描到1，此时虽然array不为空，但是array里也是1，所以还是无法抵消，把它也加入这个array,于是array变成了{1,1}（其实到这我们可以发现，array里面只可能同时存在一种数，因为只有array为空或当前扫描到的数和array里的数字相同时才把这个数字放入array）,result还是{1,1,2,1,5}

• 接下来扫描到2，把它和一个1抵消掉，至于抵消哪一个1，无所谓，array变成了{1},result是{1,1,5}接下来扫描到1，不能抵消，array变成了{1,1}，result{1,1,5}接下来扫描到5，可以将5和一个1抵消，array变成了{1},result变成了{1}

至此扫描完成了数组里的所有数，result里剩了1，所以1就是大于一半的数组。

public int majorityElement(int[] nums) {
    int major = 0;
    int majorCount = 0;
    for (int val : nums) {
        if (majorCount == 0) {
            major = val;
            majorCount++;
        } else {
            if (val == major) {
                majorCount++;
            } else {
                majorCount--;
            }
        }
    }
    
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == major) {
            count++;
            if (count > nums.length / 2) {
                return major;
            }
        }
    }
    return -1;

}

赏

谢谢你请我吃糖果

微信