转载本文请联系程序员钱宇公众号。力扣：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/GitHub：https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_31_majorityElement/Solution.java数组中出现次数超过一半的数》题目描述：数组中有一个数出现次数超过了数组长度的一半数组，请找出这个数。你可以假设数组是非空的，并且给定数组中总是有大多数元素。难度：简单示例：输入：[1,2,3,2,2,2,5,4,2]输出：2解题思路：“本文将“数组中出现次数超过一半的数”简称为“众数”。需要注意的是，众数在数学中的定义是“数组中出现次数最多的数”，与本文的定义不同。本题常见的三种解法：哈希表统计法：遍历数组nums，用HashMap统计每个数的个数，求出众数。该方法具有O(N)的时间和空间复杂度。数组排序方法：对数组nums进行排序，数组中点的元素必须是多数。MooreVotingMethod：核心思想是抵消赞成票和反对票的数量。该方法的时间复杂度和空间复杂度分别为O(N)和0(1)，是解决该问题的最佳方案。摩尔投票法：“假设输入数组nums的众数为x，数组长度为n。推论1：若众数为+1，非众数为-中等数为-1，则必然有所有数的得票数和>0。推论2：如果数组中前a个数的得票数之和=0，则剩余(n-a)个数的得票数之和数组中的数一定还是>0，即最后(n-a)个数的众数还是x。根据上面的推论，记录组的第一个元素是n1，众数是x，并且遍历并统计票数，当票数之和=0时，剩余数组的众数将保持不变，这是因为：当n1=x时：所有要抵消的数中有一半是众数x。当n1≠x：在所有要抵消的数中，模式x的数最少为0，最多为一半。利用这个特性，每一轮假设票数之和=0可以减少剩余的数组间隔。当遍历完成时，最后一轮假定的数字就是模式号。算法流程：初始化：votes=0,modex;循环：遍历数组nums中的每一个数num；当票数等于0时，假定当前票数num为众数；当num=x时，票数加1；当num!=x时，票数减1；返回值：只返回x；复杂度分析：时间复杂度O(N)：N是数组nums的长度。空间复杂度O(1)：votes变量使用恒定数量的额外空间。publicstaticintmajorityElement1(int[]nums){intx=0,votes=0;for(intnum:nums){if(votes==0)x=num;votes+=num==x?1:-1;//votes=votes+(num==x?1:-1);}returnx;}展开：由于题目说给定数组中总是有多数元素，所以本题不需要考虑数组不存在的情况占多数。如果考虑的话，需要增加一个“验证链接”，遍历数组nums来统计x的个数。如果x的个数超过数组长度的一半，则返回x；否则，返回未找到模式；时间和空间复杂度保持不变，仍然是O(N)和O(1)。publicintmajorityElement11(int[]nums){intx=0,votes=0,count=0;for(intnum:nums){if(votes==0)x=num;votes+=num==x?1:-1;}//验证x是否为多数for(intnum:nums)if(num==x)count++;returncount>nums.length/2?x:0;//没有多数则返回0}代码包com.nateshao.sword_offer.topic_31_majorityElement;importjava.util.Arrays;/***@dateCreatedby邵通杰on2021/12/517:16*@微信公众号程序员千语*@个人网站www.nateshao.cn*@bloghttps://nateshao.gitee.io*@GitHubhttps://github.com/nateshao*@Giteehttps://gitee.com/nateshao*说明：宝剑指的是Offer39.数组中出现次数超过一半的数字*说明：有是数组中的一个数一个数出现的次数超过了数组长度的一半，请求这个数*字。如果不存在则输出0。*/publicclassSolution{publicstaticvoidmain(String[]args){int[]arr={1,2,3,2,2,2,5,4,2};inti1=majorityElement1(arr);inti2=majorityElement2(arr);inti3=majorityElement3(arr);System.out.println("i="+i1);//i=2System.out.println("i2="+i2);System.out.println("i3="+i3);}/*********************精选*********************/publicstaticintmajorityElement1(int[]nums){intx=0,votes=0;for(intnum:nums){if(votes==0)x=num;votes+=num==x?1:-1;//votes=votes+(num==x?1:-1);}returnx;}/****************展开********************/publicintmajorityElement11(int[]nums){intx=0,votes=0,count=0;for(intnum:nums){if(votes==0)x=num;votes+=num==x?1:-1;}//验证x是否为多数for(intnum:nums)if(num==x)count++;returncount>nums.length/2?x:0;//没有多数时返回0}/********************************************************************************************************************************************思路：比较第一个count+1和后面的数，如果相等，则+1，否则-1，*Fin盟友，检查它是否超过一半的长度。**@paramnums*@return*/publicstaticintmajorityElement2(int[]nums){intcount=0;intcandidate=0;for(intnum:nums){if(count==0)candidate=num;count+=(num==candidate)?1:-1;}returncheckMoreThanHalf(nums,candidate)?candidate:0;}privatestaticbooleancheckMoreThanHalf(int[]array,intnumber){inttimes=0;for(inti:array){if(i==number)times++;}returntimes*2>=array.length;}publicstaticintmajorityElement3(int[]nums){Arrays.sort(nums);returnnums[nums.length/2];}}参考文献：https://leetcode-cn.com/问题/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/
