奇奇怪怪的算法

摘要：本篇blog讨论java各种非主流算法

一、求多数元素——摩尔投票法

• 核心思想

核心就是对拼消耗。

玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。

那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。

最后能剩下的必定是自己人。

• 实现

//leetcode 169 多数元素   

public int majorityElement(int[] nums) {
    //这个题一定要明白多数元素的核心，那就是其他所有元素的总数还是比不过这一个元素
    //既然这样，让所有人打起来！！但是不要内战
    //双指针不合适，因为比较极端的情况下，所有元素都不打，最后就无法判断了 
    int most=nums[0];//最多的那个数本身
    int num=0;//次数
    //从头计数
    for(int i=0;i<nums.length;i++){
        if(num==0){//触发条件：前面一轮的时候所有人都战死了
            most=nums[i];
            num++;
        }
        else if(nums[i]==most)//多个人，多一票
            num++;
        else{
            num--;
            //最多的数和当前这个数一起战死了，那么下一个最多数候选人自然就是下一趟遍历的数了。
        }
    }
    return most;
}

leetcode 229 求众数Ⅱ

赏

谢谢你请我吃糖果