本文共 1167 字，大约阅读时间需要 3 分钟。

问题 长度为 n 的数组，其中只有一个数字出现了大于等于 n/2 次，快速找到这个数字

解法一 HashMap

HashMap的key为数字，value为该数字出现的次数，不详细叙述

解法二 排序

排序后，因为该数字出现的次数大于等于n/2次，因此该数组下标为n/2的位置一定存放的是该数字，采用快速排序，时间复杂度和空间复杂度都为O($nlo{g}_{2}n$)

class Solution {
       public int majorityElement(int[] nums) {
           if(nums.length==0){
               return -1;        }        if(nums.length==1){
               return nums[0];        }        // 1.排序        quickSort(nums,0,nums.length-1);        return nums[nums.length/2];    }        public void quickSort(int[] nums,int low,int high){
           int i=low,j=high;        if(i
   
    i&&nums[j]>=temp)                    j--;                nums[i]=nums[j];                while(i
    
   

解法三 摩尔投票法

这种解法是解析的重点。

思路：数组中总数大于n/2的数叫做众数，其他的数都叫非众数，若假设众数等于1，非众数等于-1，则将所有的数加起来，最后的结果一定是大于0的，所以采用抵消的方式，用相同数量的非众数抵消众数，剩下的则全部为众数。 思想：假定某个数为候选众数，设置计数器为0，遍历数组，遇到等于候选众数的则计数器+1，不相等-1，为0时，则说明前面的数中候选众数和非众数数量抵消，如果候选众数并非真正的众数，则前面的数中至少会抵消两个非众数或者一个众数和一个非众数；如果候选众数是真正的众数，则前面的数中至少抵消了一个众数和一个非众数。因此计数器再次为0零时，剩下的一定是众数更多，缩小了范围。重新取新下标元素，这样抵消不了的众数就会导致计数器大于0，就直接返回之前赋值的元素即可。

public int majorityElement(int[] nums) {
           int count=0;        int temp=nums[0];        for(int i=0;i

转载地址：http://mjebb.baihongyu.com/