博客

牛客经典试题：数组问题

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

示例：

输入

[1,2,3,2,2,2,5,4,2]

输出

 2

思路一：


最直接的方法，就是对所有的数字进行排序，然后扫描一遍排好序的数字数组，统计每个数字出现的次数，如果某个数字出现次数超过数组元素的一半，则进行输出。但是当我们首先已经将数组元组进行排序以后，数组已经有序的时候，就不用再进行扫描了。无论这个数字是什么，都会在这个数组中第N/2的位置处（从0开始编号），一定会是这个位置的这个数字（不信的话，自己写一个数组排序后看看）。

public static int MoreThanHalfNum_Solution(int [] array) {
        if(array==null||array.length==0){
            return 0;
        }
        if(array.length==1){
            return array[0];
        }
        int sum=0;
        Arrays.sort(array);
        int tmp=array[array.length/2];
        //遍历中间的那个元素的次数是否超过数组元素的一半
        for (int value : array) {
            if (value == tmp) {
                sum++;
            }
        }
        if(sum>(array.length/2))
            return tmp;
        return 0;
    }

思路二：


如果每次删除两个不一样的数字（不管是否包含重复的数字），那么，在剩下的所有数组元素中，重复出现的元素仍然超过总数的一半，可以哦那个过不断重复这个过程，把数组中的元素总个数降低（转化为更小的问题），进而求得答案。

public static int MoreThanHalfNum_Solution2(int [] array) {
        int time=1;
        int tmp=array[0];
        for(int i=0;i<array.length;i++){
            if(time==0){
                tmp=array[i];
                time=0;
            }else{
                if(tmp==array[i]){
                    time++;
                }else{
                    time--;
                }
            }
        }
        //计算数组中tmp出现的次数
        time=0;
        for(int i=0;i<array.length;i++){
            if(tmp==array[i]){
                time++;
            }
        }
        return time>=(array.length/2)?tmp:0;


    }

人生只有走出来的美丽，没有等出来的辉煌。