leetcode169多数元素java题解（Hash）（排序）（Boyer-Moore投票）

137 阅读 0 评论 91 点赞

我是靠谱客的博主柔弱冰棍，这篇文章主要介绍leetcode169多数元素java题解（Hash）（排序）（Boyer-Moore投票），现在分享给大家，希望可以做个参考。

1.题目
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:输入: [3,2,3]输出: 3
示例 2:输入: [2,2,1,1,1,2,2]输出: 2
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element
2.想法
（1）hash
将每个数及其出现的次数用hash表存起来，最后查找大于n/2的元素
缺点：非常耗时
（2）排序
由于题目给出一定存在多数元素，故利用java api自带的Arrays类中的排序函数，是基于快排的排序，将数组排序，最终返回下标为n/2的值一定为结果。
（3）Boyer-Moore投票
如果遇到一个候选数，就将计数器加一，否则减一。只要计数器等于 0 ，就将数组中之前访问的数字全部忘记，并把下一个数字当做候选数。
原因是在遗忘前面的数字的时候，会去掉相同数目的众数和非众数。最终留下的数的计数器一定为正的。
3.图解
来源：力扣官方题解
在这里插入图片描述
4.自己题解
（1）hash

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int majorityElement(int[] nums) {
    HashMap<Integer,Integer> m=new HashMap<>();
    for(int i=0;i<nums.length;i++)
    {if(m.containsKey(nums[i])){int temp=m.get(nums[i]);temp++;m.put(nums[i],temp); }
     else{m.put(nums[i],1);}
    }
    for(Integer i:m.keySet())
     { if(m.get(i)>(nums.length/2)){return i;}}
    return -1;
    }
}

（2）排序

复制代码

1
2
3
4
5
6
7
8
class Solution{
    public int majorityElement(int nums[])
    {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

（3）Boyer-Moore投票

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution{
    public int majorityElement(int nums[])
    {	int cur=0;
     	int count=0;
        for(int i=0;i<nums.length;i++)
        {
            if(count==0){cur=nums[i];}
            if(nums[i]==cur){count++;}
            else{count--;}           
        }       
        return cur;
    }
}