算法挑战100天 - three (easy)

类别：数组

题目：https://leetcode-cn.com/problems/find-majority-element-lcci/

我的解：时间 O(n) 空间O(n)

class Solution {
     public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        Integer midSize = nums.length / 2;
        for (int i = 0; i < nums.length; i++) {
            if (map.get(nums[i]) != null) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }
        Integer result = -1;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > midSize) {
                result = entry.getKey();
            }
        }
        return result;
    }
}

最优解：时间 O(n) 空间O(1)

class Solution {
    public int majorityElement(int[] nums) {
        // 摩尔投票算法（过半才能算出）
        int temp = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == temp) {
                count++;
            } else {
                count--;
            }
            if (count == 0) {
                temp = nums[i];
                count = 1;
            }
        }

        // 验证是否满足要求
        int t = nums.length / 2 + 1;
        count = 0;
        for (int num : nums) {
            if (num == temp) count++;
            if (count == t) return temp;
        }
        return -1;
    }
}

差异点：

1.我的是利用map存储所有的元素出现次数来比较；最后再根据长度比较；思路不同；
2.没了解过摩尔算法，没往数据特性上想；摩尔算法可以让空间复杂降为O(n);