题目描述

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

输入描述

数字数组

输出描述

出现的次数超过数组长度的一半的数字

题目分析

解法一（以暴制暴） 运行时间：32ms　占用内存：528k

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length==0 || array==null) return 0;

        int temp;
        for(int i=0;i<array.length;i++){
            temp = array[i];
            int count=0;
            for(int j =0;j<array.length;j++){
                if(array[j]==temp){
                    count++;
                }
            }
            if(count>(array.length/2)){
                return temp;
            }
        }
        return 0;
    }
}

　　时间复杂度O(n^2), 遍历数组中每一个数的出现次数，第一个次数大于长度一半 的返回。

解法二 　运行时间：31ms　占用内存：629k

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array.length==0 || array==null) return 0;

        int temp=array[0],count=1;
        //找出出现次数最多的数
        for(int i=1;i<array.length;i++){
            if(array[i]==temp){
                count++;
            }else{
                count--;
            }
            if(count==0){
                temp=array[i];
                count=1;
            }
        }
        //由于可能中间夹着其他数，所以count不准确，重新确认count
        count=0;
        for(int i=0;i<array.length;i++){
            if(array[i]==temp){
               count++; 
            }
        }
        if(count*2>array.length){
            return temp;
        }
        return 0;
    }
}

　　时间复杂度Ｏ(n) （ps：虽然时间上美什么卵用），分为两步：

① 先确定 出现次数最多的数

② 遍历求该数出现的次数