題目：

數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。

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

示例：

輸入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
輸出: 2

思考：

• 方法一：投機取巧

• 將數組排序，出現次數超過一半的數字肯定在數組中間的那個位置

題解：

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

思考：

• 方法二：哈希表輔助

• 使用一個 map，key 存數組中的數字，val 存出現的次數

• 當有數字出現次數超過數組長度一半時，直接返回

題解：

class Solution {public int majorityElement(int[] nums) {Map<Integer,Integer> map = new HashMap<>();for(int num : nums){map.put(num,map.getOrDefault(num,0)+1);if(map.get(num)> nums.length>>1) return num;}return 0;}
}

思考：

• 方法三，摩爾投票法

• 眾數和非眾數投票，初始票數為 0，為 0 時假設當前數字為眾數

• 遍歷數組，是眾數 +1，不是眾數 -1，為 0 就接著繼續重新來

• 最后得到眾數

題解：

class Solution {public int majorityElement(int[] nums) {int vote = 0;int x = 0;for (int i = 0; i < nums.length; i++) {if (vote == 0) x = nums[i];if (x == nums[i]) vote++;else vote--;}return x;}
}