面试题29.数组中次数超过一半的数字

题目描述

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

• 解法一：对输入数组进行排序，然后选择中间值，如果存在次数超过一半的数字，则中间值必然是该数字，时间复杂度为O(nlogn)。

public class Solution {
    //解法一：对数组进行排序，然后选择中间值，O(nlogn)
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array==null || array.length<=0) return 0;
        Arrays.sort(array);
        int middle = array[array.length/2];
        boolean moreThanHalf = checkMoreThanHalf(array,middle);
        if(moreThanHalf) return middle;
        else return 0;
    }
    
    public boolean checkMoreThanHalf(int[] array,int val) {
        int times = 0;
        for(int i = 0; i < array.length; i++) {
            if(val==array[i]) {
                times++;
                if(times>array.length/2) return true;
            }
        }
        return false;
    } 
}

• 解法二：根据有一个数字超过一半的特点，记录两个值，一个值记录数组中的数a，另一个值记录times,如果a出现一次times++,否则times--。当times变为0时，重置a为当前检测值，times变为1。a初始值为array[0]，times初始值为1，从第二项开始遍历。O(n)

public int MoreThanHalfNum_Solution(int [] array) {
        if(array==null || array.length <= 0) return 0;
        int num = array[0];
        int times = 1;
        for(int i = 1; i < array.length; i++) {
            if(times==0) {
                num = array[i];
                times = 1;
            }
            if(array[i]==num) times++;
            else times--;
        }
        if(times>0&&checkMoreThanHalf(array,num)) {
            return num;
        }
        return 0;
    }
    
    public boolean checkMoreThanHalf(int[] array,int val) {
        int times = 0;
        for(int i = 0; i < array.length; i++) {
            if(val==array[i]) {
                times++;
                if(times>array.length/2) return true;
            }
        }
        return false;
    } 
}

• 解法三：采用快速排序中partition函数随机取得index,直到index==array.length/2，这时array[index]就是中间值。如果存在次数超过一半的数字，则中间值必然是该数字。O(n)。

public boolean checkMoreThanHalf(int[] array,int val) {
        int times = 0;
        for(int i = 0; i < array.length; i++) {
            if(val==array[i]) {
                times++;
                if(times>array.length/2) return true;
            }
        }
        return false;
    }
    
    private int RangeInt(int start,int end) {
        int random = new Random().nextInt(end-start+1);
        return random + start;
    }
    
    private void swap(int[] data,int pos1,int pos2) {
        if(pos1>=data.length||pos1<0||pos2<0||pos2>=data.length) {
            throw new IllegalArgumentException("参数不合法");
        }
        int temp = data[pos1];
        data[pos1] = data[pos2];
        data[pos2] = temp;
    }
    
    private int partition(int[] data,int start,int end) {
        //随机选择一个位置，将比其小的元素左排，比其大的元素右排
        if(data==null || data.length <= 0 || start <0 || end>=data.length) {
            throw new IllegalArgumentException("参数不合法");
        }
        int index = RangeInt(start,end);
        int i = start,j = end+1;//i为左指针，j为右指针
        int val = data[index];
        swap(data,start,index);
        while(true) {
            while(i+1<data.length&&data[++i]<val) if(i==end) break;//直到data[i] >= val
            while(j-1>=0&&data[--j]>val) if(j==start) break;//直到data[i] <= val
            if(i >= j) break;
            swap(data,i,j);
        }
        swap(data,start,j);
        return j;//data[start...j-1]<=data[j]<=data[j+1...end]达成
    }
    
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array==null || array.length <= 0) return 0;
        int middle = array.length>>1; 
        int start = 0,end = array.length-1;
        int index = partition(array,start,end);
        while(index!=middle) {
            if(index<middle) {
                start = index+1;
                index = partition(array,start,end);
            }
            if(index>middle) {
                end = index-1;
                index = partition(array,start,end);
            }
        }
        if(checkMoreThanHalf(array,array[index])) return array[index];
        else return 0;
    }