Sponsored
Sponsored
This approach leverages a hashmap to count the occurrences of each element in the input array. We iterate through the array once to populate the hashmap and then make another pass to find all elements whose count is greater than ⌊n/3⌋. While this method is straightforward and simple to implement, it uses extra space proportional to the number of unique elements.
Time Complexity: O(n), where n is the length of the array since we go through the list of numbers twice.
Space Complexity: O(n) to handle the possible maximum unique elements.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4using namespace std;
5
6vector<int> majorityElement(vector<int>& nums) {
7 unordered_map<int, int> countMap;
8 int limit = nums.size() / 3;
9 for (int num : nums) {
10 countMap[num]++;
11 }
12 vector<int> result;
13 for (auto& entry : countMap) {
14 if (entry.second > limit) {
15 result.push_back(entry.first);
16 }
17 }
18 return result;
19}
20
21int main() {
22 vector<int> nums = {3, 2, 3};
23 vector<int> result = majorityElement(nums);
24 for (int num : result) {
25 cout << num << " ";
26 }
27 return 0;
28}In this C++ solution, we use an unordered_map to count occurrences of each element in the array. We iterate through 'nums' to build the map, and then again to construct a result vector containing elements that appear more than ⌊n/3⌋ times. The unordered_map allows us to handle counting efficiently due to its average O(1) time complexity for insert and access operations.
The Boyer-Moore Voting Algorithm is optimized for finding the majority element which appears more than n/2 times. Here, we extend it to handle the case for n/3 by maintaining up to two potential candidates, since at most two elements can qualify for appearing more than ⌊n/3⌋ times. In the first pass, we identify the element candidates by attempting to cancel them out against others. A second pass is required to confirm the counts of these candidates to ensure they appear more than ⌊n/3⌋ times.
Time Complexity: O(n), going through elements twice.
Space Complexity: O(1) as no additional space is needed apart from variables.
This C program applies Boyer-Moore to locate up to two potential majority elements. Initial counts start at zero, and when a candidate is different, the count decreases. If zeroed, a new candidate is established. A further check verifies that these candidates surpass ⌊n/3⌋ occurrences.