数组中出现超过一半的数字

时间限制：1秒 空间限制：32768K 热度指数：127962

本题知识点： 数组

 算法知识视频讲解

题目描述

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

题目地址

public class Solution {
    
   public void swap(int[] arr,int a,int b){
        int t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }
    public int Partition(int[] arr,int l,int r){
        int p = arr[l];//设置哨兵位置
        int i = l;
        int j = r;
        while (i < j){
            while (arr[j] >= p && i < j){
                j--;
            }
            if (i<j){
                swap(arr,i,j);
            }
            while (arr[i] <= p && i < j){
                i++;
            }
            if (i<j){
                swap(arr,i,j);
            }
        }
        return i;
    }
    public int MoreThanHalfNum_Solution(int[] arr) {
        if(arr.length == 0 || arr ==null)
            return 0 ;
        int l = 0 ;
        int r = arr.length-1;
        int mid = l + ((r-l)>>1);
        int index = Partition(arr,l,r);
        while(index != mid){
            if(index>mid){
                r = index-1;
                index = Partition(arr,l,r);
            }else{
                l = index+1;
                index = Partition(arr,l,r);
            }
        }
        int result = arr[mid];
        int count = 0;
        for(int i = 0 ;i<arr.length;i++){
            if(arr[i]==result)
                count++;
        }
        if(count*2<=arr.length)
            return 0;
        return  result;
    }
}