刷题日记03补充

书接上回，上次做了一道求数组中多数的问体，我用了两种方法，一个是自己想出来的比较麻烦的，一个是看了题解用Map做的。根据评论区一个高手建议，我补充一种摩尔投票的解题方法，很好用。

public static int majorityElement(int[] nums){
        int ans = 0;
        int count = 0;
        //摩尔投票
        for (int i = 0; i < nums.length; i++) {
            if(count == 0){
                ans = nums[i];
            }
            if(ans == nums[i]){
                count++;
            }else{
                count--;
            }
        }
        return ans;
}

摩尔算法可以理解为对数组进行抵消、抵消、抵消，直到不能够抵消。那什么时候可以抵消呢？摩尔投票算法是基于这个事实：每次从序列中选取两个数据进行比较，如果不相同就把两个数据删除，最后剩一个或多个相同元素，那么该数字就是我们要找的多数。

比如我们查询一个数组为[2,2,1,1,1,2,2]，遍历该数组，同时我们创建两个数组分别为arr和result，arr用来存储当前不能被抵消的数字，result用来表示抵消后剩余数组。

第一个数字为2，前面没有数字可以抵消，arr = {2}，result = {2,2,1,1,1,2,2}。
第二个数字为2，和前面的2不能抵消，arr = {2,2}，result = {2,2,1,1,1,2,2}。
第三个数字为1，和前面的2抵消，arr = {2}，result = {2,1,1,2,2}。
第四个数字为1，和前面的1抵消，arr = {}，result = {1,2,2}。
第五个数字为1，前面没有数字了，arr = {1}，result = {1,2,2}。
第六个数字为2，和前面的1不能抵消，arr = {}，result = {2}。
第七个数字为2，前面没数字了。arr = {2}，result = {2}。

所以最后剩个2就是多数。简单来说这就相当于多派战斗，就是比人数，打的时候都是极限一换一，最后剩的就是人多的一派。

除去冗余关系：实际代码中没有array，也没有result，因为我们不需要。由于前面提到array里只可能同时存储一种数字，所以我们用major来表示当前array里存储的数，count表示array的长度,即目前暂时无法删除的元素个数，最后扫描完所有的数字，array和result变成一样了，都表示“最后还是无法删除的数字”。

第一个数字为2，前面没有数字可以抵消，major = 2，count = 1。
第二个数字为2，和前面的2不能抵消，major = 2，count = 2。
第三个数字为1，和前面的2抵消，major= 2。这时候major不用变，因为查到1的时候这个1和前面的2抵消了，还剩一个2，所以arr中还是2，因此major = 2，count = 1。
第四个数字为1，和前面的1抵消，major = 2，count =0。此时count = 0,其实可以理解为扫到的元素都抵消完了，这里可以暂时不改变major的值。
第五个数字为1，前面没有数字了，major = 1，count = 1。
第六个数字为2，和前面的1不能抵消，major暂时不变，major = 1，count= 0。
第七个数字为2，前面没数字了。major= 2，count = 1。

经过上述遍历，我们可以发现，当count = 0的时候，major才会变化，变成当前遍历值。如果count不为0的时候，遍历的值和major相等则count++，遍历的值和major不相等则count--。

刷题日记03补充

全站热榜