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.
This is another easy puzzle at https://leetcode.com/problems/majority-element/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution { public: int majorityElement(vector<int>& nums) { unordered_map<int, int> dict; int n = nums.size(); for (int i = 0; i < n; i ++) { if (dict.count(nums[i])) { dict[nums[i]] ++; } else { dict[nums[i]] = 1; } } for (int i = 0; i < n; i ++) { if (dict[nums[i]] > n / 2) { return nums[i]; } } } }; |
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> dict;
int n = nums.size();
for (int i = 0; i < n; i ++) {
if (dict.count(nums[i])) {
dict[nums[i]] ++;
} else {
dict[nums[i]] = 1;
}
}
for (int i = 0; i < n; i ++) {
if (dict[nums[i]] > n / 2) {
return nums[i];
}
}
}
};We use a unordered_map to store the number of appearances. Then a second loop checks if the counter is bigger than n/2 times. However the compiler may warn you that the function may not return values in all paths.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
238 wordsloading...
Last Post: How to Check for Duplication in C++?
Next Post: How to Reverse Bits for 32-bit Unsigned Integer in C/C++?
