LeetCode Top-100 T169-求衆數

題目描述：

給定一個大小為 n 的數組，找到其中的衆數。衆數是指在數組中出現次數大于 ⌊ n/2 ⌋ 的元素。

你可以假設數組是非空的，并且給定的數組總是存在衆數。

示例 1:

    輸入: [3,2,3]

    輸出: 3

示例 2:

    輸入: [2,2,1,1,1,2,2]

    輸出: 2

解題思路：

通過周遊數組nums，将數組元素作為key元素put到hashmap中，最後在對比value值傳回key值

代碼1

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> hm = new HashMap<>();
        for (int num:nums) {
            if (!hm.containsKey(num)) {
                hm.put(num,1);
            } else {
                hm.put(num,hm.get(num)+1);
            }
            if (hm.get(num) > nums.length/2) {
                System.out.println(num);
            }
        }
    }
}      

代碼2：可以使用sort排序時

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}      

class Solution {
    public int majorityElement(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        for (int i : nums) {
            if (stack.empty() || i == stack.peek()) {
                stack.push(i);
            } else {
                stack.pop();
            }
        }
        return stack.peek();
    }
}