博文中会简要介绍Leetcode P0169题目分析及解题思路。
“Majority Element”这道题比较基础，使用HashTable记录每个元素出现的个数，当某个元素的出现次数大于一半的时候返回这个元素。
Given an array of size n, find the majority element. The majority element is the element that appears more than
⌊ n/2 ⌋times.You may assume that the array is non-empty and the majority element always exist in the array.
以下是Java的题解代码实现。
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> num2CountMap = new HashMap<>();
int N = nums.length;
for (int num: nums) {
num2CountMap.put(num, num2CountMap.getOrDefault(num, 0)+1);
if (num2CountMap.get(num) > N/2)
return num;
}
return 0;
}
}
以下是C++的题解代码实现。
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> num2count;
int N = nums.size();
for (int num: nums) {
++num2count[num];
if (num2count[num] > N/2)
return num;
}
return 0;
}
};