给定一个大小为n的数组，找到其中的众数。众数是指在数组中出现次数大于⌊n/2⌋的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例1:
输入:[3,2,3]输出:3
示例2:
输入:[2,2,1,1,1,2,2]输出:2思路
思路一：
利用哈希表的映射，储存数组中的数字以及它们出现的次数，当众数出现时，返回这个数字。
思路二：
因为众数是出现次数大于n/2的数字，所以排序之后中间的那个数字一定是众数。即nums[n/2]为众数。但是在计算比较大的数组时，时间会超过限制。
思路三：
分治法，将整个数组分成两个部分，先分别筛选出这两部分中出现次数最多的数，记为left和right，如果left等于right，则返回left，如果left不等于right，则left和right都是最终结果的候选，此时需要遍历整个数组考察left和right出现的次数，出现次数较多的就是最终返回的结果。
思路四：
摩尔投票算法,先将第一个数字假设为众数，然后把计数器设为1，比较下一个数和此数是否相等，若相等则计数器加一，反之减一。然后看此时计数器的值，若为零，则将当前值设为候选众数。以此类推直到遍历完整个数组，当前候选众数即为该数组的众数。
代码实现packageArray;importjava.util.HashMap;/***169.MajorityElement（求众数）*给定一个大小为n的数组，找到其中的众数。众数是指在数组中出现次数大于⌊n/2⌋的元素。*你可以假设数组是非空的，并且给定的数组总是存在众数。*/publicclassSolution169{publicstaticvoidmain(String[]args){Solution169solution169=newSolution169();int[]nums=newint[]{3,2,3};System.out.println(solution169.majorityElement_4(nums));}/***利用哈希表的映射，储存数组中的数字以及它们出现的次数，当众数出现时，返回这个数字。**@paramnums*@return*/publicintmajorityElement(int[]nums){HashMap<Integer,Integer>map=newHashMap<>();for(intnum:nums){Integercnt=map.get(num);if(cnt==null){cnt=1;}else{cnt++;}if(cnt>nums.length/2){returnnum;}map.put(num,cnt);}return0;}/***因为众数是出现次数大于n/2的数字，所以排序之后中间的那个数字一定是众数。即nums[n/2]为众数。但是在计算比较大的数组时，时间会超过限制。**@paramnums*@return*/publicintmajorityElement_2(int[]nums){intn=nums.length;for(inti=0;i<n-1;i++){for(intj=0;j<n-1-i;j++){if(nums[j]>nums[j+1]){inttemp=nums[j];nums[j]=nums[j+1];nums[j+1]=temp;}}}returnnums[n/2];}/***分治法，将整个数组分成两个部分，先分别筛选出这两部分中出现次数最多的数，记为left和right，如果left等于right，则返回left*如果left不等于right，则left和right都是最终结果的候选，此时需要遍历整个数组考察left和right出现的次数，出现次数较多的就是最终返回的结果。**@paramnums*@return*/publicintmajorityElement_3(int[]nums){returnfind(nums,0,nums.length-1);}publicintfind(int[]nums,intbegin,intend){if(begin==end){returnnums[begin];}else{intmid=(begin+end)/2;intleft=find(nums,begin,mid);intright=find(nums,mid+1,end);//左右两部分的众数相同则这个数是这部分的众数if(left==right){returnleft;}else{//左右两部分的众数不相同则这两个数都有可能是这部分的众数,那么遍历这个数组，看一下哪个数字的出现次数多intcountLeft=0;intcountRight=0;for(inti=begin;i<=end;i++){if(nums[i]==left){countLeft++;}elseif(nums[i]==right){countRight++;}}if(countLeft>countRight){returnleft;}else{returnright;}}}}/***摩尔投票算法,先将第一个数字假设为众数，然后把计数器设为1，比较下一个数和此数是否相等，若相等则计数器加一，反之减一。*然后看此时计数器的值，若为零，则将当前值设为候选众数。以此类推直到遍历完整个数组，当前候选众数即为该数组的众数。**@paramnums*@return*/publicintmajorityElement_4(int[]nums){intmaj=nums[0];intcount=1;for(intnum:nums){if(maj==num){count++;}else{count--;if(count==0){maj=num;count=1;}}}returnmaj;}}posted@2018-09-0116:24武培轩阅读(...)评论(...)编辑收藏
