Leetcode刷题之旅--剑指 Offer 39. 数组中出现次数超过一半的数字

题目描述：

思路：第一种思路用Map存储出现次数。

class Solution {
    public int majorityElement(int[] nums) {
        HashMap <Integer,Integer> map =new HashMap();
        int mid=nums.length>>1;
        for(int i=0;i<nums.length;i++){
            int tem=nums[i];
            if(map.containsKey(tem)){
                int count=map.get(tem);
                if(count>=mid) return tem;
                else{
                    map.put(tem,count+1);
                }
            }else{
                map.put(tem,1);
            }
        }
        return nums[0];
    }
}

第二种：排序，输出数组中间值。
第三种：摩尔投票法：总体思路就是–有一个计数器，假设第一个数是众数计数器+1，下一个数如果等于当前假定众数，计数器加1，否则计数器-1.每当计数器数值为0时，都要重新假设众数。剩下的最后一个假定众数即为所求。
此外如果题目中没有给出一定存在大于一半的数，那么就需要最后遍历一次数组，看得到的假定众数是否超过一半。

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

这种做法十分巧妙！！！！

最后

以上就是漂亮铃铛为你收集整理的Leetcode刷题之旅--剑指 Offer 39. 数组中出现次数超过一半的数字的全部内容，希望文章能够帮你解决Leetcode刷题之旅--剑指 Offer 39. 数组中出现次数超过一半的数字所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。