/**
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You
may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
Constraints:
n == nums.length
1 <= n <= 5 * 10⁴
-10⁹ <= nums[i] <= 10⁹
Follow-up: Could you solve the problem in linear time and in O(1) space?
Related Topics数组 | 哈希表 | 分治 | 计数 | 排序
👍 1557, 👎 0
*/
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> numMap = new HashMap<>();
int maxNum = 0, result = 0;
for (int i = 0; i < nums.length; i += 2) {
if (i == nums.length - 1) {
if (numMap.containsKey(nums[i])) {
numMap.put(nums[i], numMap.get(nums[i]) + 1);
} else if (numMap.size() == 0) {
return nums[i];
}
} else {
if (nums[i] == nums[i + 1]) {
int curNum = numMap.getOrDefault(nums[i], 0);
numMap.put(nums[i], curNum + 2);
}
}
}
for (Map.Entry<Integer, Integer> entry : numMap.entrySet()) {
if (entry.getValue() > maxNum) {
maxNum = entry.getValue();
result = entry.getKey();
}
}
return result;
}
}
//leetcode submit region end(Prohibit modification and deletion)
