题目描述

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

题解一

对于排序的数组，数组中出现次数超过一半的数字一定会出现在数组的中间。于是先将数组排序，然后输出中位数即可。但是由于输入的数组不一定满足要求，所以别忘了检查得到的数字是否真的在数组中出现的次数超过一半。

时间复杂度为O(nlogn)，空间复杂度为O(1)。

public int majorityElement(int[] array) {
    Arrays.sort(array);
    int res = array[array.length >> 1];
    return Check(array, res) ? res : 0;
}

private boolean Check(int[] array, int number) {
    int times = 0;
    for (int num : array)
        if (num == number) times++;
    return times > array.length >> 1;
}

题解二

一个直观的解法是使用哈希表。遍历一遍数组，将数组中每个元素出现的次数存入哈希表，然后遍历哈希表，找出出现次数大于一半的数字。

时间复杂度为O(n)，空间复杂度为O(n)。

public int majorityElement(int[] array) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int num : array) {
        if (!map.containsKey(num))
            map.put(num, 1);
        else map.put(num, map.get(num)+1);
    }
    for (HashMap.Entry<Integer, Integer> entry : map.entrySet()) {
        if (entry.getValue() > array.length/2)
            return entry.getKey();
    }
    return 0;
}

题解三

考虑数组的特性，若数组中有一个数字出现的次数超过了数组长度的一半，那么数组中第 n/2 大的数字一定是这个数字。

可以借助快排的思想来寻找特定的下标，这里我们需要寻找的下标就是 n/2，每次 Partition 都可以将 pivot 放置到其对应的位置，且所有小于pivot的数字都在 pivot 左边，大于 pivot 的数字都在 pivot 右边。排序后数组中的下标为数组长度一半的数字即为数组中第 n/2 大的数字（数组的中位数）。

为了找到这个数字，我们可以使用递归，如果 pivot 的坐标小于 n/2，那么继续在 pivot 右边进行查找；如果 pivot 的坐标大于 n/2，那么继续在 pivot 左边进行查找；如果 pivot 的坐标刚好等于 n/2，那么就返回数组中对应的数字。

最后别忘了检查得到的数字是否真的在数组中出现的次数超过一半，毕竟上述算法得到的只是这个数组中第 n/2 大的数字，并不保证这个数字出现次数超过一半。

时间复杂度为O(n)，空间复杂度为O(1)。

public int majorityElement(int[] array) {
    int length = array.length;
    int middle = length >> 1;
    int pivotPos = Partition(array, 0, length-1);
    while (pivotPos != middle) {
        if (pivotPos > middle)
            pivotPos = Partition(array, 0, pivotPos-1);
        else pivotPos = Partition(array, pivotPos+1, length-1);
    }
    return Check(array, array[pivotPos]) ? array[pivotPos] : 0;
}

private int Partition(int[] array, int left, int right) {
    int pivot = array[left];
    while (left < right) {
        while (left < right && array[right] >= pivot) right--;
        array[left] = array[right];
        while (left < right && array[left] <= pivot) left++;
        array[right] = array[left];
    }
    array[left] = pivot;
    return left;
}

private boolean Check(int[] array, int number) {
    int times = 0;
    for (int num : array)
        if (num == number) times++;
    return times > array.length >> 1;
}

题解四

还有另外一种巧妙的方法。遍历数组，同时维护两个变量：一个是数组中的一个数字，另一个是次数。在遍历数组时，第一个数字作为守方， 设置count=1，接下来的数字进行攻击。在遇到相同元素时守方即count加1，遇到不同元素时count-1。在count为0时，新的数字成为新的守方，接受接下来的攻击。

若数组中有一个出现次数超过一半的数字，那么它一定是最终的胜利者。但也有可能不存在这与的数字，所以在结束之后也要像之前一样进行检查。

时间复杂度为O(n)，空间复杂度为O(1)。

class Solution {
    public int majorityElement(int[] array) {
        if (array.length == 0)
            return 0;
        int victor = Integer.MIN_VALUE, count = 0;
        for (int value : array) {
            if (victor == Integer.MIN_VALUE && count == 0) {
                victor = value;
                count++;
            } else if (victor == value) {
                count++;
            } else {
                count--;
                if (count == 0) victor = Integer.MIN_VALUE;
            }
        }
        return Check(array, victor) ? victor : 0;
    }

    private boolean Check(int[] array, int number) {
        int times = 0;
        for (int num : array)
            if (num == number) times++;
        return times > array.length >> 1;
    }
}