題目描述

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

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

示例 1：

輸入：nums = [3,2,3]
輸出：3

示例 2：

輸入：nums = [2,2,1,1,1,2,2]
輸出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

進階：嘗試設計時間復雜度為 O(n)、空間復雜度為 O(1) 的算法解決此問題。

解題思路

統計每個元素出現的次數，可以想到哈希表，這里用unordered_map，鍵存放元素，值存放元素出現的次數。

遍歷數組，將每個元素都加入哈希表中，同時要維護最大的值。最后將最大值輸出即可。

代碼實現

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int, int> countNum;int result = 0, count = 0;for (int i : nums) {++countNum[i]; // 這里用前置遞增是為了節省內存，后置遞增也可以// 維護最大的值if (countNum[i] > count) {result = i;count = countNum[i];}}return result;}
};