找出數組中出現次數大于一半的數字 Java實作 劍指offer

題目描述：

數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。例如輸入一個長度為9的數組{1,2,3,2,2,2,5,4,2}。由于數字2在數組中出現了5次，超過數組長度的一半，是以輸出2。如果不存在則輸出0

解題思路：

第一種最簡單，進行快速排序，然後取出最中間的數字，并且用這個數字周遊一遍數組，看看該數出現次數是不是大于數組長度的一半（實作代碼如下，快速排序法）；

第二種方法：思想：對數組同時去掉兩個不同的數字，到最後剩下的一個數就是該數字。如果剩下兩個，那麼這兩個也是一樣的，就是結果）；最終剩下的設兩個數組下标索引（start,end,y一頭一尾），比較下标出的元素，

若兩個元素不一樣，start--;end++;

若兩個元素一樣，end--;

最終會出現start與end相等或者end-start=1兩種情況，對于前者，需要判斷剩下的這個數字周遊一遍數組，看看該數出現次數是不是大于數組長度的一半；若是後者，直接比較兩個數字是否相等，相等即傳回該數字，不相等集傳回0；

快速排序法：

public class Solution {

    private int[] data;

    public int MoreThanHalfNum_Solution(int [] array) {

        data=array;

        startSort(0,data.length-1);

        int key=data[(data.length-1)/2];

        int count=0;

        for(int i=0;i<data.length;i++){

            if(data[i]==key){

                count++;

            }

        }

        if(count>(data.length)/2)

            return key;

        else

            return 0;

    }

    public void startSort(int start,int end){

        if(start>=end) return;

        int index=partition(start,end);

        startSort(start,index-1);

        startSort(index+1,end);

    }

    public int partition(int start,int end){

        int key=data[start];

        while(start<end){

            while(data[end]>=key&&start<end){

                end--;

            }

            data[start]=data[end];

            while(data[start]<=key&&start<end){

                start++;

            }

            data[end]=data[start];

        }

        data[start]=key;

        return start;

    }

}

另一種方法：

public class Solution {

    private int[] data;

    public int MoreThanHalfNum_Solution(int [] array) {

        data=array;

        int result=0;

        int start=0;

        int end=array.length-1;

        while(end-start>1){

            if(array[start]!=array[end]){

                end--;

                start++;

            }

            else{

                end--;

            }

        }

        if(end-start==1){

            if(array[start]==array[end]){

                result=array[start];

            }

        }

        else{

            if(count(array[start])){

                result=array[start];

            }

        }

        return result;

    }

    public boolean count(int value){

        boolean result=false;

        int count=0;

        for(int i=0;i<data.length;i++){

            if(value==data[i])

            count++;

        }

        if(count>((data.length)/2))

            result=true;

        return result;

    }

}