Java寻求众数前言一、例题、答案1、例题2、答案a、HashMapB、序列c、堆栈d、比武招亲e、RandomF、分治总结的参考文献
前言
在Java中求出一个数组的众数，可以使用HashMap、堆栈等数据结构。
一、例题、答案1、例题数组中出现的数字超过数组长度的一半。 请找到这个数字。
可以假设数组不是空的，并且给定数组中始终存在许多元素。
样本1:
输入：[1、2、3、2、2、2、5、4、2]
输出： 2
2、答、解HashMap用HashMap快速解题，记录各要素出现的个数，如果个数大于len/2，则认为那是众数。
用publicintmajorityelement (int [ ] nums ) { //Hash Map快速问题//map记录num的长度，len/2 MapInteger，Integer record=new HashMap哦for(intI=0； i len； I ) intn=record.getordefault (nums [ I ]，0 ) 1； if(nlen/2 )返回编号[ I ]； Record.put(nums[I]，n )； }返回0； ) b、排序可以对数组进行排序，但众数一定在中间。
publicintmajorityelement2(int [ ] nums )//排序，值必须为中间Arrays.sort ) nums； return nums[nums.length/2]； } C、堆栈为空或堆栈顶部==num时，将num放入堆栈；
否则，不将num放入堆栈中，将堆栈的最高位元素从堆栈中取出；
这样最后堆栈的要素都是众数。
publicintmajorityelement3(int [ ] nums )/)在堆栈中进入所有元素，遇到不同的元素时发出堆栈。 因为个数大于数组的一半，所以最终剩下的元素是返回值。 dequeintegerrecord=new linked list (； for(intI=0； i nums.length； I ) if (！ record.isempty(|record.peek )==nums[i] ) record.push )==nums[i] )； 继续； } record.pop (； } return record.peek (； } D、比武招亲专名又称zyddr票，根据数组元素记录当前值的票数，相等时在票数上加1，否则加-1。 减少到0后，重新记录新值。
将数组分成两组。 一个是众数，另一个是非众数。 众数的个数不是众数的个数。 所以最终记录的数量是众数。
publicintmajorityelement4(int [ ] nums ) (/比武招亲int res=0，count=0； for(intnum:nums ) if ) count==0) ) { res=num； 计数=1； 继续； } count =num==res？ 1 : -1； }返回RES； (e、Random将数组分为模式数和非模式数两组。 众数的个数不是众数的个数。 所以随机选择一个数对其次数进行计数，看其次数是否为len/2，随机随机查找众数。
//randompublicintmajorityelement5(int [ ] nums )//个数就这么多，所以随机选择一个数来计数出现次数，如果个数超过len/2，则进入RES； wile(true ) { Random rand=new Random； intindex=getrandom(rand，0，nums.length )； if(getcount(nums，nums[index] ) nums.length/2 ) return nums[index]； }公共int getrandom (random rand，int min，int max ) returnrand.nextint ) max-min )； }公共int getcount (int [ ] nums，int n ) { int count=0； for(intnum:nums ) { count =num==n？ 1 : 0； }返回计数； ) f、分割统治数组减半，或者如果两组数组的模式数相同，则为nums数组整体的模式数； 一定是一半数组的最频值成为nums数组整体的最频值，或者两侧的最频值不同的情况下，计数各区间的最频值的个数。
//分治publicintmajorityelement6(int [ ] nums ) ) /如果将数组减半，则两侧的模式数相同，或一定一半有模式数。 如果两侧的模式数不同，则各区间的模式数returngetresbyrecursion ) numumumum } publicintgetcountbylr (int [ ] nums，int n，int left，int rirint for(intI=left； i=right； I ) { count =n==nums[i]？ 1 : 0； }返回计数； } publicintgetresbyrecursion (int [ ] nums，int left，int right ) if ) left==right ) return nums[left]；//注意mid的取法mid！=(左右)/2或(右左)/2左，而不是右/2； int mid=(左光线)/2； intle ftn=getresbyrecursion (nums，left，mid )； intrightn=getresbyrecursion (nums，mid 1，right )； if(leftn！=rightn (returngetcountbylr (nums，leftN，left，mid ) getcountbylr ) nums，rightn，mid 1，right )？ leftN : rightN； }返回leftn； )总结1 ) HashMap，快速访问。 时间： o (n )，空间： o (n ) n ) )。
2 )排序，时间： o (nlog 2n )，空间： o (1) (1) ) ) ) ) ) )。
3 )堆栈(time:o(n )、Space:O(n ) n ) ) )。
4 ) zyddr选票，时间： o (n )，空间： o (1) (1) ) )。
5 ) Random、time:o () n2 )、Space:O(1) )1)虽然事件的复杂度高，但这是最坏的情况，但平均情况下的执行时间不是很高，取最频值的概率为1/2
6 )分治、t(n )=2t ) n/2 ) 2n、time:o ) nlog2n )、space:o ) log2n ) )。
参考文献[1] Leetcode原题
[2]官方详细情况