【LeeCode精选】169. 求众数

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

解析：

题目咋一看感觉稳了有木有，解题思路出奇的清晰啊：构造一个hash存储结构，将数组中元素值作为key，该元素出现的次数作为value存放在hash中，遍历hash找出第一个value大于n/2的key返回即可。

    public static int majorityElement(int[] nums) {
        Map<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer temp = null;
            hash.put(nums[i], null != (temp = hash.get(nums[i]))?++temp:1);
        }
        for (Integer in : hash.keySet()) {
            if (hash.get(in) > (nums.length/2)) {
                return in;
            }
        }
        return 0;
    }

可以看出如上思路的代码实现时间复杂度O(n),空间复杂度也为O(n)。

那么，问题来了，有没有更高效（无论从时间上和空间上）的方式来解决这个问题呢？

答案是有的，采用摩尔投票法，其算法思想为：将数组中的第一个数假设为众数，然后进行统计其出现的次数，如果遇到同样的数，则计数器自增1，否则计数器自减1，如果计数器减到了0，则更换下一个数字为候选者。

    public static int majorityElement1(int[] nums) {
        //假设第一个节点为目标节点
        int temp = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            //若上次循环累积次数为零，则更新当前节点为目标节点并设累计次数为1
            if (0 == count) {
                temp = nums[i];
                count = 1;
            }else {
                //否则累加或者累减
                if (nums[i] == temp) {
                    count++;
                }else {
                    count--;
                }
            }
        }
        return temp;
    }

可见此实现的时间复杂度为O(n)，而空间复杂度则缩减为了O(1)。