Dare2Solve
Given an integer array nums
, find all elements that appear more than n/3
times, where n
is the size of the array. The task is to return these elements in a list. The solution should ensure that each element in the result list is unique.
The problem asks for elements that appear more than n/3
times, where n
is the size of the array. Since the majority elements must appear frequently, we can use a counting approach to track occurrences of each element. To ensure that an element appears only once in the result, we can use a flagging mechanism.
Use of Hash Maps:
unordered_map
in C++):
res2
) tracks the frequency of each element in the array.res
) is used to flag elements that have already been added to the result list to avoid duplicates.Iteration:
res
, skip further processing for that element.res2
.n/3
, add it to the result list and flag it in res
.Return Result:
n/3
times.O(n), where n
is the size of the array. The algorithm iterates through the array once, performing constant-time operations for each element.
O(n), due to the additional space used by the two hash maps to store element frequencies and flags.
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
unordered_map<int, bool> res;
unordered_map<int, int> res2;
vector<int> final;
for (int i = 0; i < nums.size(); i++) {
if (res[nums[i]]) continue;
res2[nums[i]]++;
if (res2[nums[i]] > nums.size() / 3) {
res[nums[i]] = true;
final.push_back(nums[i]);
}
}
return final;
}
};
// Usage Example
// int main() {
// Solution sol;
// vector<int> nums = {3, 2, 3, 4, 2, 2, 2};
// vector<int> result = sol.majorityElement(nums);
// for (int num : result) {
// cout << num << " ";
// }
// return 0;
// }
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
res = {}
res2 = {}
final = []
for num in nums:
if res.get(num):
continue
res2[num] = res2.get(num, 0) + 1
if res2[num] > len(nums) // 3:
res[num] = True
final.append(num)
return final
# Usage Example
# sol = Solution()
# nums = [3, 2, 3, 4, 2, 2, 2]
# result = sol.majorityElement(nums)
# print(result) # Output: [2]
class Solution {
public List<Integer> majorityElement(int[] nums) {
Map<Integer, Boolean> res = new HashMap<>();
Map<Integer, Integer> res2 = new HashMap<>();
List<Integer> finalResult = new ArrayList<>();
for (int num : nums) {
if (res.getOrDefault(num, false)) continue;
res2.put(num, res2.getOrDefault(num, 0) + 1);
if (res2.get(num) > nums.length / 3) {
res.put(num, true);
finalResult.add(num);
}
}
return finalResult;
}
// Usage Example
// public static void main(String[] args) {
// Solution sol = new Solution();
// int[] nums = {3, 2, 3, 4, 2, 2, 2};
// List<Integer> result = sol.majorityElement(nums);
// System.out.println(result);
// }
}
var majorityElement = function(nums) {
let res=[];
let res2=[];
let final=[];
for(let i=0;i<nums.length;i++){
if(res[nums[i]]) continue;
if(res2[nums[i]]) res2[nums[i]]++;
else res2[nums[i]] = 1;
if(res2[nums[i]] > (nums.length/3)){
res[nums[i]] = true;
final.push(nums[i]);
};
}
return final;
};
``