Sponsored
Sponsored
This approach involves counting the frequency of each element using a HashMap (or a Dictionary). We store each element as a key and maintain its count as the value. Finally, we determine which key has a count greater than half the length of the array.
Time Complexity: O(n) as we traverse the array twice, Space Complexity: O(n) since we use an additional data structure to store counts.
1#include <iostream>
2#include <unordered_map>
3#include <vector>
4using namespace std;
5
6int majorityElement(vector<int>& nums) {
7 unordered_map<int, int> countMap;
8 for (int num : nums) {
9 countMap[num]++;
10 }
11 int majorityCount = nums.size() / 2;
12 for (auto& [num, count] : countMap) {
13 if (count > majorityCount) {
14 return num;
15 }
16 }
17 return -1; // never hit due to problem assumptions
18}
19
20int main() {
21 vector<int> nums = {2, 2, 1, 1, 1, 2, 2};
22 cout << majorityElement(nums);
23 return 0;
24}In C++, we use an unordered_map to maintain the counts of each element. After counting, we iterate over this map to return the number with the highest frequency.
The Boyer-Moore Voting Algorithm is an efficient solution that processes the array in a single pass. It maintains a count for the majority candidate. At the end of the loop, since the majority element exists, the candidate will be the majority element.
Time Complexity: O(n) as it traverses the array once, Space Complexity: O(1) because no extra space is used except for variables.
1
Boyer-Moore works by selecting a potential candidate and adjusting a counter up and down as it processes the list. If the counter becomes zero, a new candidate is considered. The majority presence guarantees the candidate is correct.