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

题目描述

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

这是一道考察优化时间和空间效率的题目。

解法一：

看到这道题目时第一反应就是如果这个数组是有序的话，那我们只要查看中间那个数字的数量是否大于长度的一半便可以了。若中间那个数字的数量大于长度的一半，则这个数字就是所要求的数字；若不大于，则没有符合要求的数字。

由于数组是无序的，需要先进行排序。采用最快的快速排序，时间复杂度为O(NlogN)。之后统计中间数字次数，时间复杂度O(logN)，综上，整个算法的时间复杂度为O(NlogN)。

解法二：

那么有没有空间换时间的做法呢？很明显我们可以记录下每个数字出现的次数，最后查看是否存在要求的数字即可。使用Map较为方便，key存储数字值，value存储出现的次数。在数组中读取一个数字后，若Map中不存在相应数字则在Map中添加该数字，并将次数置为1；若已存在该数字，则将原次数加一。代码如下：

public class Solution {
    public static int MoreThanHalfNum_Solution(int [] array) {
        //必须考虑非法输入保证健壮性
        if(array == null || array.length <= 0)
            return 0;
        Map<Integer, Integer> count = new HashMap<Integer, Integer>();
        for(int i = 0; i < array.length; i++) {
            if(!count.containsKey(array[i])) {
                count.put(array[i], 1);
            }
            else {
                int value = count.get(array[i]);
                count.put(array[i], ++value);
            }
        }
        for(Map.Entry<Integer, Integer> entry : count.entrySet()) {
            if(entry.getValue() > array.length / 2) {
                return entry.getKey();
            }
        }
        return 0;
    }
}

解法三：

解法三不需要额外的空间浪费仍然可以达到与解法二相同的时间复杂度。
数组中一个数字的次数超过总长的一半，说明它的次数比其他所有数字的和还要多。
1.我们可以记录下数组第一个数的值与次数，依次遍历数组，若接下来的数字与记录的数字相同，则次数加一；若接下来的数字与记录的数字不同，则次数减一。
2.当次数为0时，保存下一个数字，并将次数置为1
3.若最后获得了一个次数大于1的数字，则判断这个数字是否符合要求。若没有得到这样一个数字，则返回0.

（若一个数字的次数超过一半，则一定会在最后被得到；但是最后得到的数字，出现次数不一定超过一半）

public class Solution {
    public static int MoreThanHalfNum_Solution(int [] array) {
        //非法输入判断
        if(array == null || array.length <= 0)
            return 0;
        int times = 1;
        int number = array[0];
        //查看是否存在有可能次数大于数组长度一半的数字
        for(int i = 1; i < array.length; i++) {
            if(times <= 0) {
                number = array[i];
                times = 0;
            }
            if(array[i] == number) {
                times++;
            }
            else { 
                times--;
            }
        }
        //判断该数字次数是否大于数组长度一半
        if(times > 0) {
            int count = 0;
            for(int i = 0; i < array.length; i++) {
                if(array[i] == number)
                    count++;
            }
            if(count > array.length / 2)
                return number;
            else
                return 0;
        }
        else
            return 0;
    }

解法四：

利用Partition函数（详见博客[快速排序算法])。Partition函数可以在数组中任取一个数字，将数组中比该数字小的均放置在该数字左边，比该数字大的均放在该数字右边。最后返回该数字的下标index。我们可以利用这个特性：
1.设数组长度一半为middle。数组起点为start，终点为end。
2.若index大于middle，说明中位数在start到index之间。更新end = index - 1；
若index小于middle，说明中位数在index到end之间。更新start = index + 1；
若index等于middle，说明array[index]即为中位数。
3.判断取得的中位数是否满足次数大于长度一半。
该算法的时间复杂度为O(N)

public class Solution {
    public static int MoreThanHalfNum_Solution(int[] array) {
        int start = 0, end = array.length - 1;
        int index = Partition(array, start, end);
        int middle = array.length / 2;
        while(index != middle) {
            if(index > middle) {
                end = index - 1;
                index = Partition(array, start, end);
            }   
            else {
                start = index + 1;
                index = Partition(array, start, end);
            }

        }
        int times = 0;
        for(int i = 0; i < array.length; i++) {
            if(array[i] == array[index]) 
                times++;
        }
        if(times > array.length / 2)
            return array[index];
        else
            return 0;
    }
    public static int Partition(int[] array, int start, int end) {
        Random rand = new Random();
        int index = rand.nextInt(end - start + 1) + start;
        Swap(array, index, end);
        int small = start - 1;
        for(index = start; index < end; index++) {
            if(array[index] < array[end]) {
                small++;
                if(small != index) 
                    Swap(array, small, index);
            }
        }
        small++;
        Swap(array, small, end);
        return small;
    }
    public static void Swap(int[] array, int a, int b) {
        int tmp;
        tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
}

解法三与解法四虽然时间复杂度相同，但是解法四更改了输入数据，在不允许更改输入数据的情况下则只能选择解法三。