主要元素

继续算法

题目:如果数组中多一半的数都是同一个，则称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。

示例 1：

输入：[1,2,5,9,5,9,5,5,5]
输出：5

这题很久之前在剑指offer上看过,这次算重新复习一遍
有人把这种题目解题思路叫摩尔投票法,有人叫幸存者法,还有叫守阵地法...
我喜欢守幸存者法这个名字

思路:
首先用一个数字survivor来保存幸存者方,用一个数字count来计算幸运者幸运值
规则:如果遇到相同数字代表相同阵营,count++;
如果遇到不同数字,则幸存者count--;
如果count=0,则幸存者被取代.

注意如果存在超过一般的数字,那么这个数字肯定是幸存者,但是幸存者不一定是个数超过一般的那个.比如12213,幸存者是3,但是3个数没有超过一半.因此我们在得到幸存者后要进行验证

为什么说如果存在超过一半的数字,那么这个数字肯定是幸存者?因为如果极端的说,若其个数超过一半了,那么就算间隔着如12131514161,其他数字全由1出力干掉不用其他数字帮忙,最后也可以幸存1个

public int majorityElement(int[] nums) {
        if (nums==null||nums.length==0){
            return -1;
        }
        if (nums.length==1){
            return nums[0];
        }

        int sur=nums[0];
        int count=1;//存活计数
        int index=1;//索引位置
        //找出最后幸存的数
        for (;index<nums.length;index++){
            if (nums[index]==sur){
                count++;
            }else {
                count--;
                if (count==0){
                    sur=nums[index];
                    count=1;
                }
            }
        }
        //验证这个数是否超过一半
        count=0;//个数计数,判断是否超过一半
        for (index=0;index<nums.length;index++){
            if (nums[index]==sur){
                count++;
                if (count>nums.length/2){
                    return sur;
                }
            }
        }

        if (count>nums.length/2){
            return sur;
        }else {
            return -1;
        }

    }

也有想过其他方法,比如利用hash特性,但是cpu消耗比较大 上面是hash下面是幸存者法,hash的代码在下面

    public int majorityElement(int[] nums) {
       Map<Integer,Integer> map=new HashMap<>();
        for (Integer i: nums
             ) {
            map.put(i,map.get(i)==null?1:map.get(i)+1);
            if (map.get(i)>nums.length/2)
                return i;
        }
        return 0;
    }

如果大家觉得我的方法不好,也可以去leetcode上看看别的人的方法,总能找到适合你的🤭https://leetcode-cn.com/problems/find-majority-element-lcci/comments/