剑指Offer_编程题_数组中出现次数超过一半的数字

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0

方法一

先利用sort函数排序，从第一个元素查找到中间元素，如果存在相隔数组长度一半及以上位置的元素相等的话（好难描述…），判定成功，返回该元素。这个方法操作比较麻烦，需要考虑数组左右，并且需要考虑数组的长度奇偶。

牛客AC代码如下

import java.util.Arrays;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
         
         
        int temp=0;
        if(array.length==0||array==null){
            return 0;
        }else if(array.length==1)
            return temp=array[0];
         else if(array.length==2&&array[0]!=array[1])
             return temp=0;
        else{
            Arrays.sort(array);
            for (int i = 0; i < array.length/2; i++) {
                if(array[i]==array[array.length-1-i] || (array[i]==array[array.length/2]&&array.length%2==0))
                     temp=array[i];
                if(array[array.length/2]==array[array.length-1] && array.length%2!=0)
                    temp=array[array.length/2];
            }
            return temp;
        }
         
             
         
         
     
    }
}

方法二

建立一个count方法统计数组中每个元素出现的次数num，并返回。在判定方法里调用count方法，如果num大于数组长度一半，判定成功。这个方法不需要考虑数组奇偶，比较好理解。

牛客AC代码如下

import java.util.Arrays;
public class Solution {
        private int count(int x,int[] array) {
		// TODO 自动生成的方法存根
		int num=0;
		for (int i = 0; i < array.length; i++) {
			if(x==array[i])
				num++;
		}
		
		return num;

	}
public int MoreThanHalfNum_Solution(int [] array) {
	int num=0;
	for (int i = 0; i < array.length; i++) {
		if(count(array[i], array)>array.length/2){
			num=array[i];
		}
			
		
	}
	return num;
	
	
	
} 
}