首页 > 试题广场 > 数组中出现次数超过一半的数字
[编程题]数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
推荐
方法一:采用用户“分形叶”思路(注意到目标数 超过数组长度的一半,对数组同时去掉两个不同的数字,到最后剩下的一个数就是该数字。如果剩下两个,那么这两个也是一样的,就是结果),在其基础上把最后剩下的一个数字或者两个回到原来数组中,将数组遍历一遍统计一下数字出现次数进行最终判断。
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int length=array.length;
            if(array==null||length<=0){
                return 0;
            }
            
            if(length==1){
                return array[1];
            }
            
            int[] tempArray=new int[length];
            for(int i=0;i<length;i++){
                tempArray[i]=array[i];
            }
            
            for(int i=0;i<length;i++){
                //后面需要用零来代表抹除数字,所以对0时做特殊处理
                if(tempArray[i]==0){
                    continue;
                }
                
                for(int j=i+1;j<length;j++){
                    if(tempArray[i]!=tempArray[j]&&tempArray[j]!=0){
                        tempArray[i]=0;//此处用0代表抹去该数字
                        tempArray[j]=0;
                        break;
                    }
                    
                }
            }
            
            for(int i=0;i<length;i++){
                System.out.println(tempArray[i]);
            }
            
            //找出未被抹去的数字
            int result=0;
            for(int i=0;i<length;i++){
                if(tempArray[i]!=0){
                    result=tempArray[i];
                    break;
                }
            }
            
            int times=0;
            for(int i=0;i<length;i++){
                if(result==array[i]){
                    
                    times++;
                }
            }
            
            if(times*2<length){
                result=0;
            }
            return result;
    }
}

方法二:剑指offer解法二(个人觉得与方法一基本就是同一个意思,异曲同工之妙)
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int length=array.length;
        if(array==null||length<=0){
            return 0;
        }
        
        int result=array[0];
        int times=1;
        for(int i=1;i<length;i++){
            if(times==0){
                result=array[i];
                times=1;
            }else{
                if(array[i]==result){
                    times++;
                }else{
                    times--;
                }
            }
        }
        
        times=0;
        for(int i=0;i<length;i++){
            if(result==array[i]){
                times++;
            }
       }
            
       if(times*2<length){
           result=0;
       }
       return result;
    }
}


编辑于 2015-06-19 17:18:47 回复(86)
思路一:数组排序后,如果符合条件的数存在,则一定是数组中间那个数。(比如:1,2,2,2,3;或2,2,2,3,4;或2,3,4,4,4等等)
这种方法虽然容易理解,但由于涉及到快排sort,其时间复杂度为O(NlogN)并非最优;
参考代码如下:
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) 
    {
        // 因为用到了sort,时间复杂度O(NlogN),并非最优
    	if(numbers.empty()) return 0;
        
        sort(numbers.begin(),numbers.end()); // 排序,取数组中间那个数
        int middle = numbers[numbers.size()/2];
        
        int count=0; // 出现次数
        for(int i=0;i<numbers.size();++i)
        {
            if(numbers[i]==middle) ++count;
        }
        
        return (count>numbers.size()/2) ? middle :  0;
    }
};
思路二:如果有符合条件的数字,则它出现的次数比其他所有数字出现的次数和还要多。
在遍历数组时保存两个值:一是数组中一个数字,一是次数。遍历下一个数字时,若它与之前保存的数字相同,则次数加1,否则次数减1;若次数为0,则保存下一个数字,并将次数置为1。遍历结束后,所保存的数字即为所求。然后再判断它是否符合条件即可。
参考代码如下:
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) 
    {
    	if(numbers.empty()) return 0;
        
        // 遍历每个元素,并记录次数;若与前一个元素相同,则次数加1,否则次数减1
        int result = numbers[0]; 
        int times = 1; // 次数
        
        for(int i=1;i<numbers.size();++i)
        {
            if(times == 0)
            {
                // 更新result的值为当前元素,并置次数为1
                result = numbers[i];
                times = 1;
            }
            else if(numbers[i] == result)
            {
                ++times; // 相同则加1
            }
            else
            {
                --times; // 不同则减1                
            }
        }
        
        // 判断result是否符合条件,即出现次数大于数组长度的一半
        times = 0;
        for(int i=0;i<numbers.size();++i)
        {
            if(numbers[i] == result) ++times;
        }
        
        return (times > numbers.size()/2) ? result : 0;
    }
};

编辑于 2016-08-23 16:04:29 回复(38)
时间复杂度是O(n)才对

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int n = numbers.size();
        if (n == 0) return 0;
        
        int num = numbers[0], count = 1;
        for (int i = 1; i < n; i++) {
            if (numbers[i] == num) count++;
            else count--;
            if (count == 0) {
                num = numbers[i];
                count = 1;
            }
        }
        // Verifying
        count = 0;
        for (int i = 0; i < n; i++) {
            if (numbers[i] == num) count++;
        }
        if (count * 2 > n) return num;
        return 0;
    }
};
编辑于 2015-07-28 13:13:40 回复(68)
java巧解
import java.util.Arrays;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
    	Arrays.sort(array);
        int count=0;
        
        for(int i=0;i<array.length;i++){
            if(array[i]==array[array.length/2]){
                count++;
            }
        }
        if(count>array.length/2){
            return array[array.length/2];
        }else{
            return 0;
        }
        
    }
}
时间复杂度O(n)
方法一:用hashMap
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
    	HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        
        for(int i=0;i<array.length;i++){
            
            if(!map.containsKey(array[i])){
               map.put(array[i],1); 
            }else{
                int count = map.get(array[i]);
                map.put(array[i],++count);
            }
        }
        Iterator iter = map.entrySet().iterator();
        while(iter.hasNext()){
            Map.Entry entry = (Map.Entry)iter.next();
            Integer key =(Integer)entry.getKey();
            Integer val = (Integer)entry.getValue();
            if(val>array.length/2){
                return key;
            }
        }
        return 0;
}
方法二:基于快排思想
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
   if(array.length<=0)
            return 0;
        
        int start = 0;
        int length = array.length;
        int end  = length-1;
		int middle = length>>1;
        
        int index = Partition(array,start,end);
        
        
        while(index!=middle){
            
            if(index>middle){
            	index = Partition(array,start,index-1);
            }
            else{
            	index = Partition(array,index+1,end);
            }
        }
        int result = array[middle];
        
        int times = 0;
        for(int i=0;i<length;++i){
            if(array[i] == result)
                times++;
        }
        if(times*2<length){
        	System.out.println(times);
            return 0;
        }else{
            return result;
        }
    }
       public int Partition(int[] array,int start,int end){
        int flag = (array[start]+array[end])/2;
        
        while(start<end){
            while(array[end]>flag){
                end--;
            }
            swap(array,start,end);
            while(array[start]<=flag){
                start++;
            }
            swap(array,start,end);
        }
        return start;
    }
    public void swap(int[] array,int num1,int num2){
        int temp =array[num1];
        array[num1] =array[num2];
        array[num2] =temp;
    }
}
方法三:基于数组特点
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
      if(array.length<=0){
            return 0;
        }
        int result = array[0];
        int times = 1;
        
        for(int i=0;i<array.length;i++){
            if(times==0){
                result = array[i];
                times =1;
            }else if(array[i]==result)
                times++;
             else
                times--;
        }
        int time = 0;
        for(int i=0;i<array.length;++i){
            if(array[i] == result)
                time++;
        }
        if(time*2<array.length){
        	System.out.println(time);
            return 0;
        }else{
            return result;
        }
    }
}

编辑于 2016-09-03 14:44:48 回复(25)
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int n = numbers.size();
        //map 记录出现次数
        map<int, int> m;
        int count;
        for (int i = 0; i < n; i++) {
            count = ++m[numbers[i]];
            if (count > n/2) return numbers[i];
        }
        return 0;
    }
};

发表于 2017-04-18 16:08:58 回复(26)

python的三种解法

# -*- coding:utf-8 -*-
class Solution:
    """第一种,用python的标准库collections"""
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        from collections import Counter
        count =  Counter(numbers).most_common()
        if count[0][1] > len(numbers)/2.0:
            return count[0][0]
        return 0

class Solution:
    """第二种,假设有这个数字,那么它的数量一定比其它所有数字之和还要多,按照这个思路得出num,然后验证
    """
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if not numbers:
            return 0
        num = numbers[0]
        count = 1
        for i in range(1, len(numbers)):
            if numbers[i] == num:
                count += 1
            else:
                count -= 1
            if count == 0:
                num = numbers[i]
                count = 1
        count = 0
        for i in numbers:
            if i == num:
                count += 1
        return num if count > len(numbers) / 2.0 else 0

class Solution:
    """对列表排序,计算下标为len/2(即中间位置)的数字数量即可"""
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        # 对列表进行快排
        left = 0
        right = len(numbers) - 1
        stack = [right, left]
        while stack:
            low = stack.pop()
            high = stack.pop()
            if low >= high:
                continue
            less = low - 1
            mid = numbers[high]
            for i in range(low, high):
                if numbers[i] <= mid:
                    less += 1
                    numbers[less], numbers[i] = numbers[i], numbers[less]
            numbers[less + 1], numbers[high] = numbers[high], numbers[less + 1]
            stack.extend([high, less+2, less, low])
        # 验证
        count = 0
        length = len(numbers) // 2
        for i in numbers:
            if i == numbers[length // 2]:
                count += 1
        return numbers[length // 2] if count > length / 2.0 else 0
发表于 2018-01-26 18:03:43 回复(2)
分析思路:
如果这个题目是排好序的数组,那么我们就很容易统计出每个数字出现的次数。题目给出的数组没有说是排好序的,因此我们需要先给它排序。 排序的时间复杂度是O(nlogn) 。最直观的算法通常不是面试官满意的算法,我们需要找出更快的算法。

****其中一种思路是:基于Partition函数的O(n)算法
我们回到题目本身分析,就会发现前面的思路并没有考虑到 数组的特性 :数组中有一个数字出现的次数超过了数组长度的一半。如果我把这个数组排序,那么排序之后位于数组中间的数字一定就是那个出现次数超过数组一半的数字。也就是说,这个数字就是统计学上的中位数,即长度为n的数组中第n/2的数字。 我们有成熟的O(n)的算法得到数组中任意第K大的数字
这种算法是受快速排序算法的启发。在随机快速排序算法中,我们现在数组中随机选择一个数字,然后调整数组中数字的顺序,使得比选中的数字小的数字都排在它的左边,比选中的数字大的数字都排在它的右边。如果这个选中的数字的下标刚好是n/2,那么这个数字就是数组的中位数。如果它的下标大于n/2,那么中位数应该位于它的左边,我们可以接着在它的左边部分的数组中查找。如果它的下标小于n/2,那么中位数应该位于它的右边,我们可以接着在它的右边部分的数组中查找。这是一个典型的递归过程,实现代码如下:
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int length=numbers.size(); 
        if(numbers.empty()||length<0)
            return 0;
        int middle=length>>1;
        int start=0;
        int end=length-1;
        //int index=partition(numbers,length,start,end);       
        int index=partition(numbers,start,end);               
        while(index!=middle)
         { 
            if(index>middle)
             {
               end=index-1;
               index=partition(numbers,start,end);  
             }
            else
             {
               start=index+1;
               index=partition(numbers,start,end);                
             }
         }
        int result=numbers[middle];           //这里的只是得到了第middle=n/2大的数字,但总个体是否超过一段还需要判断
        if(!CheckMoreThanHAlf(numbers,length,result))    //此时需要检查result的值的个数是否大于整个数组的一半
            return 0;
        return result;
    }
    
    
    int partition(vector<int> input,int low,int high)
      {
        int pivotkey=input[low];   //pivot:枢纽
        //这里的pivotkey也可以是[low,high]区间一个随机数,也可以是三数取中,九数取中,详情见<<大话数据结构>>
        //int pivotkey=input[RandInRange(start,end)];
        while(low<high)
          {
            while(low<high&&pivotkey<input[high])
                high--;
            swap(&input[low],&input[high]);
            while(low<high&&pivotkey>=input[low])
                low++;
            swap(&input[low],&input[high]);
          }  
        return low;
      }
    
    /*这个partition是优化了不必要的交换,将swap用赋值替换
    int partition(vector<int> &input, int begin, int end)
     {
       int low = begin;
       int high = end;
       int pivot = input[low];
       while (low < high)
        {
          while (low < high&&pivot <= input[high])
             high--;
          input[low] = input[high];         //优化不必要的替换
          while (low < high&&pivot >= input[low])
             low++;
          input[high] = input[low];         //优化不必要的替换
        }
          input[low] = pivot;
          return low;
      }
    */
    
    bool CheckMoreThanHAlf(vector<int> numbers,int length,int result)    //检查result的值的个数是否大于整个数组的一半
        {
           int times=0;
           for(int i=0;i<length;++i)
             {
                if(numbers[i]==result)
                    times++;
             }
           bool isMoreThanHalf=true;
           if(times*2<=length)
               isMoreThanHalf=false;
           return isMoreThanHalf;
        }
    
    void swap(int *a,int *b)   //交换两个数
        {
           int temp;
           temp=*a;
           *a=*b;
           *b=temp;
        }
    /*下面的partition是剑指offer上的实现,考虑的很详情,但是没有上面的好理解
    int RandInRange(int a,int b)    //产生一个[a,b]范围内的随机整数
        {
           int c;
           c=a+rand()%(b-a+1);
           return c;
        }
    
    int partition(vector<int>& data,int length,int start,int end)    //partition函数是为了找出数组中第K大的数字 
       {
          if(data.empty()||length<0||start<0||end>=length)
              return 0;  //throw new std::exception("Invakid Parameters");
          int index=RandInRange(start,end);          
          swap(&data[index],&data[end]);   
          int small=start-1;
          for(index=start;index<end;++index)
            {
               if(data[index]<data[end])
                 {
                   ++small;
                   if(small!=index)
                        swap(&data[index],&data[small]); 
                 }
            }
           ++small;
           swap(&data[small],&data[end]); 

           return small;
       }
       */
};
编辑于 2017-07-05 10:47:04 回复(8)
public int MoreThanHalfNum_Solution(int [] array) {
        HashMap<Integer,Integer> hashmap=new HashMap<>();
		for(int i=0;i<array.length;i++){
			Integer tmp=hashmap.get(array[i]);
			if(tmp==null){
				hashmap.put(array[i], 1);
                tmp=1;
			}else{
				hashmap.put(array[i], tmp+1);
			}
            if(tmp+1>array.length/2) return array[i];
		}
        /*
		Iterator iter=hashmap.entrySet().iterator();
		while(iter.hasNext()){
			Map.Entry<Integer,Integer> entry=(Entry<Integer, Integer>) iter.next();
			if(entry.getValue()>array.length/2){
				return entry.getKey();
			}
		}
        */
		return 0;
    }

编辑于 2015-09-14 16:49:11 回复(8)
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array==null||array.length==0){
            return 0;
        }
        //最开始假设我方有一个士兵,如果遇到一个不一样的则为敌人,count--,
        //如果是零了,那么将敌方士兵放在阵地上,没有剑指offer里面的代码优雅,但是
        //比较适合我这种基础薄弱的理解
        int result=array[0];
        int count=1;
        for(int i=1;i<array.length;i++){
           if(result==array[i]){
               count++; }else if(result!=array[i]){
               count--; }
           if(count==0){
               result=array[i];
               count=1;
           }
        }
        int time = 0;
        for(int i=0;i<array.length;++i){
            if(array[i] == result)
                time++;
        }
        if(time*2<=array.length){
            System.out.println(time);
            return 0;
        }else{
            return result;
        }
    }
}

发表于 2017-01-05 19:47:30 回复(2)
# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        dict = {}
        for no in numbers:
            if not dict.has_key(no):
                dict[no] = 1
            else:
                dict[no] = dict[no] + 1
            if dict[no] > len(numbers)/2:
                return no
        return 0
发表于 2017-09-07 23:04:52 回复(3)
import java.util.HashMap;
import java.util.Map;
/*
 * 利用map存值,找出存在最多的数字,若大于长度一半,返回此数,否则返回0
 */
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
	    if(array.length==0||array==null)
		    return 0;
    	Map<Integer,Integer> map=new HashMap<Integer,Integer>();
    	for(int i=0;i<array.length;i++){
    		if(map.containsKey(array[i])){
    			map.put(array[i], map.get(array[i])+1);
    		}else{
    			map.put(array[i], 1);
    		}
    	}
    	for (Map.Entry<Integer, Integer> entry : map.entrySet()) {  
    		if(entry.getValue()>array.length/2)
    			return entry.getKey();
    	}  
		return 0;
    }
}

编辑于 2016-08-23 09:51:23 回复(9)
该题目与测试用例有点不匹配,题目明确说了,数组中有一个数字出现的次数超过了数组长度的一半,设数组长度为n,则该数字至少出现n/2+1次, 也就是说输入必须要满足这样的条件,即数组包含至少重复n/2+1次的数字, 而测试用例却没有保证这样的条件,并且对没有满足这样的条件的输入要求输出为0. 
因此题目应该建议改成:判断正整数数组中是否存在至少重复n/2+1的数字,若存在,输出该数字,若不存在,输出0.
发表于 2015-08-20 16:47:19 回复(2)
俗称”打擂“算法

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> a) {
    	int x, cnt = 0, n = a.size();
        for(int i = 0; i < n; ++i){
            if(cnt == 0 || a[i] == x) x = a[i], cnt++;
            else --cnt;
        }
        cnt = 0;
        for(int i = 0; i < n; ++i)  if(a[i] == x) ++cnt;
        return (cnt * 2 > a.size() ? x : 0);
    }
};
编辑于 2016-06-17 17:02:41 回复(9)

使用JavaScript语言的一种“另类”解法:

function MoreThanHalfNum_Solution(numbers) {
    for (let i = 0; i < numbers.length; i++) {
        if (numbers.join().split(numbers[i]).length - 1 > numbers.length / 2) {
            return numbers[i];
        }
    }
    return 0;
}
发表于 2018-07-24 14:35:22 回复(1)
解法一:
利用vector 的sort()
首先将容器中的数字排序,因为要求输出重复次数大于数组大小一般的书,排序结束后,相同的数字都在相邻位置,直接判断数组当前位置的 数字 与数组位置+数组一半长度  位置的数字是否相等,相等则输出该数字

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {

        int size = numbers.size() /2;
        sort(numbers.begin(),numbers.end());
        for(int i =0;i+size<numbers.size();i++)
            {
            if(numbers[i]==numbers[i+size])
                return numbers[i];
        }
        return 0; 
    }
};
解法二
空间换时间:
先用map保存每个数字在数组中出现的次数,再找到出现次数超过一半的
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
       map<int,int> numbersMap;
        for(int i=0;i<numbers.size();i++){
            numbersMap[numbers[i]]+=1;

        }
        int max =numbers.size()/2;
        int number=0;
        for(map<int,int>::iterator it=numbersMap.begin();it!=numbersMap.end();it++){
            if(max<(it->second)){
                number=it->first;
            }
        }
        return number;
    }
};

编辑于 2019-02-21 22:57:49 回复(1)
书上用的partition函数,不知道为什么没有人写,可能比别的方法复杂吧,我写了一个
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array==null||array.length==0)
return 0;
int middle=array.length>>1;
int start=0;
int end=array.length-1;
int index=Partition(array,start,end);

while(index!=middle){
if(index>middle){
end=index-1;
ndex=Partition(array,start,end);
}
else{
start=index+1;
index=Partition(array,start,end);
}
}
int result=array[middle];
if(!CheckMoreThanHalf(array,result))
result=0;
return result;
}

public static boolean CheckMoreThanHalf(int array[],int number){
int times=0;
for(int i=0;i<array.length;++i){
if(array[i]==number)
times++;
}
boolean isMoreThanHalf=true;
if(times*2<=array.length){
isMoreThanHalf=false;
}
return isMoreThanHalf;
}
public static int Partition(int array[],int start,int end){
int pivotkey=(int)start+(int)Math.random()*(end-start);
while(start<end){
while(start<end&&array[end]>=array[pivotkey])
end--;
int temp=array[start];
array[start]=array[end];
array[end]=temp;
while(start<end&&array[start]<=array[pivotkey])
start++;
temp=array[start];
array[start]=array[end];
array[end]=temp;
}
return start;
}
}
编辑于 2016-07-14 15:09:18 回复(0)
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty()) return 0;
    	unordered_map<int, int> map;
        for(int i = 0; i < numbers.size(); i++){
            map[numbers[i]]++;
        }
 

        int len = (numbers.size() >>1);
        for ( auto &it : map ){
            if(it.second > len){
                return it.first;
            }
        }
        return 0;
    }
};

发表于 2015-09-27 17:21:02 回复(2)
class Solution {
public:                 //觉得好就给个赞吧
	int MoreThanHalfNum_Solution(vector<int> numbers) {
		if (numbers.size() == 0)return 0;
		if (numbers.size() == 1)return numbers[0];
		int i, k = numbers[0], count = 1;
		for (i = 1; i < numbers.size(); ++i)
		{
			if (numbers[i] == k)
				count++;
			else
			{
				count--;
				if (count == 0)
				{
					count = 1;
					k = numbers[i];
				}
			}
		}
		if (count > 1 || (count == 1 && k != numbers[i - 1]))
			return k;
		return 0;
	}
};

发表于 2016-07-25 22:46:33 回复(4)

参考多数投票算法的思想

先随意确定一个候选元素,cnt是候选元素的计数,当遇到一个跟候选元素不同的元素时,两者数量上抵消一个,cnt减1。一旦cnt变成0,就重新找一个候选元素。
当遇到一个与候选元素不同的元素时,就要抵消。
对于候选元素和当前元素,可能存在两种情况:

  1. 两者中有一个正好是主要元素;
  2. 两者都不是主要元素。

对于情况1,抵消过后,主要元素还是主要元素;对于情况2,可以说主要的元素的地位得到了巩固。所以算法最终能找到主要元素。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int n = numbers.size();
        if(n == 0){
            return 0;
        }
        int cnt = 1;
        int majority = numbers[0];
        for(int i = 1; i < n; ++i){
            if(numbers[i] == majority){
                ++cnt;
            }else{
                --cnt;
            }
            if(cnt == 0){
                majority = numbers[i];
                cnt = 1;
            }
        }
        cnt = 0;
        for(int number : numbers){
            if(number == majority){
                ++cnt;
            }
        }
        return cnt > n/2 ? majority : 0;
    }
};

另一种有意思的解法。(C++)

三向切分+中间向两边扩散查找

class Solution {
public:
    int MoreThanHalfNum_Solution(vector numbers) {
        int n = numbers.size();
        if(n == 0){
            return 0;
        }
        quickSortIn3Way(numbers, 0, n-1);
        int mid_idx = n / 2;
        int mid_val = numbers[mid_idx];
        // 找到 mid_val的数量,判断是否大于n/2
        int i = mid_idx, j = mid_idx;
        while (i >= 0 && j < n) {
            if (numbers[i] != mid_val && numbers[j] != mid_val) {
                break;
            }
            if (numbers[i] == mid_val) {
                --i;
            }
            if (numbers[j] == mid_val) {
                ++j;
            }
        }
        return j - i + 1 - (numbers[i] != mid_val) - (numbers[j] != mid_val) > mid_idx ? mid_val : 0;
    }
    // 对于包含大量重复数字的数组,使用三向切分排序
    void quickSortIn3Way(vector &a, int lo, int hi){
        if (lo >= hi) {
            return;
        }
        int i = lo + 1;
        int lt = lo;
        int gt = hi;
        int base = a[lo];
        while (i <= gt) {
            if (a[i] < base) {
                swap(a[lt++], a[i++]);
            } else if (a[i] > base) {
                swap(a[i], a[gt--]);
            } else {
                ++i;
            }
        }
        quickSortIn3Way(a, lo, lt - 1);
        quickSortIn3Way(a, gt + 1, hi);
    }
};
编辑于 2019-04-11 16:12:34 回复(0)
用一个数组为每个数字设置一个计数器,当计数值超过数组长度一半则返回该数字。 若遍历整个数字后仍无此种数值,则返回0。 
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int len=array.length;
        int[] count=new int[]{0,0,0,0,0,0,0,0,0,0};
        for(int i=0;i<len;i++){
            count[array[i]]++;
            if((count[array[i]]*2)>len){
                return array[i];
            }
        }
        return 0;
    }
}

编辑于 2017-10-05 11:52:58 回复(2)
import java.util.Arrays;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length == 0 || array == null){
            return 0;
        }
        Arrays.sort(array);
        int mid = array[array.length/2];
        int j = 0;
        for (int i : array){
            
            if (i == mid){
                j++;
            }
        }
        return j > array.length/2 ? mid : 0;
    }
}

先将数组进行快排,如果数组中有一个数字出现的次数超过数组长度的一半,那么快排后数组中间的数就一定是这个数字。遍历快排后的数组,如果最中间的数的个数大于数组长度的一半,则输出这个数,否则输出0;
发表于 2016-03-12 21:46:58 回复(6)