169. 多數元素

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

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

示例1：

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

示例2：

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

來源：力扣（LeetCode） 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

題解：

本題利用HashMap和經過排序后返回的中位數就是眾數其實都比較好像，這個摩爾投票法真的秀的人頭皮發麻，這里依次記錄三種解法。

具體代碼如下：

利用HashMap：

class Solution {public int majorityElement(int[] nums) {int num = nums.length / 2;int result = 0;Map<Integer, Integer> map = new HashMap<>();//先遍歷一邊數組，將元素作為Key，元素出現次數作為Valuefor (int i = 0; i < nums.length; i++) {map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);}//題目說明只有一個數出現次數大于數組長度一半，找到直接返回即可Set<Map.Entry<Integer, Integer>> entries = map.entrySet();for (Map.Entry<Integer, Integer> entry : entries) {if (entry.getValue() > num) {result = entry.getKey();break;}}return result;} }

利用排序后中位數即是眾樹：

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

利用摩爾投票法：

摩爾投票法有兩個推論

• 若記 眾數 的票數為 +1 ，非眾數 的票數為 ?1 ，則一定有所有數字的 票數和 >0
• 若數組的前 個數字的 票數和 =0 ，則 數組剩余 個數字的 票數和一定仍 >0 ，即后 個數字的 眾數仍為 。

所以，我們可以從第一個元素開始，假定第一個元素就是眾數，我們每次遇到這個元素就+1?，其他元素就-1，如果votes==0，利用推論可以棄掉前面的元素，重新以當前元素開始，假定當前元素為眾數繼續向后遍歷，最后返回x即是該數組眾數。

class Solution {public int majorityElement(int[] nums) {int x = 0, votes = 0;for (int num : nums) {if (votes == 0) x = num;votes += num == x ? 1 : -1;}return x;} }

總結

以上是生活随笔為你收集整理的从当前元素继续寻找_169. 多数元素的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。