面试题 29

1 题目描述

数组中有一个数字出现的次数超过数组长度的一般，请找出这个数字

2 算法描述

数组中有一个数组出现的次数超过了一半，如果把这个数组排序，那么排序之后位于数组中间的数字一定就是那个出现次数超过一半的数字。有成熟的 O(n)算法可以得到数组中任意第 K 大的数字。
利用快速排序的 partition 方法，在数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小的数字都排在他的左边，比选中数字大的数字都排在它的右边，如果选中的数字的最终位置是 n/2，那么这个数就是数组中的中位数。

出现次数超过一半的数字必定是次序列排序后的中位数
利用 partition 方法可以在 O(n) 的的时间复杂度下找到数组中第 K 大的数字。

3 java实现

public class MoreThanHalfNum{
    public static void main(String[] args) {
        int result=moreThanHalfNum(new int[]{1,2,3,4,5,6,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,7,7,7,7,7,7,7,7,7});
        System.out.println(result);
    }

    public static int moreThanHalfNum(int[] arrays){
        int middle=arrays.length>>1;
        int start=0;
        int end=arrays.length-1;
        int index=partition(arrays,start,end);
        while(index!=middle){
            if(index>middle){
                index=partition(arrays,start,index-1);
            }else{
                index=partition(arrays,index+1,end);
            }
        }
        return arrays[middle];  
    }
    public static int partition(int[] arrays,int start,int end){
        int pivot=arrays[start];
        int temp_1;
        while(start<end){
            while(arrays[end]>=pivot&&end>start) end--;
            temp_1=arrays[end];
            arrays[end]=arrays[start];
            arrays[start]=temp_1;
            while(arrays[start]<=pivot&&end>start) start++;
            temp_1=arrays[start];
            arrays[start]=arrays[end];
            arrays[end]=temp_1;
        }
        return end; 
    }
}

4 解法 2

利用数组的特点，数组中一个数字出现的次数超过了数组长度的一般，也就是说他出现的次数比其他所有数字出现的次数的和还要多。因此我们可以考虑在便利数组的时候保存两个值，一个是数组中的一个数数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之间保存的数字相同，则次数加 1；如果下一个数字和我们之间保存的数字不同，则次数减 1，如果次数为零，我们需要保存下一个数字，并把次数设置为 1.

public class MoreThanHalfNum{
    public static void main(String[] args) {
        int result=moreThanHalfNum(new int[]{1,2,3,3,2,3,3});
        System.out.println(result);
    }


    public static int moreThanHalfNum(int[] arrays){
        int result=arrays[0];
        int times=0;
        for(int i=1;i<arrays.length;i++){
            if(times==0){
                times=1;
                result=arrays[i];
            }else{
                if(result==arrays[i]){
                    times++;
                }else{
                    times--;
                }
            }
        }
        return result;
    }
}