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.
1using System;
2using System.Collections.Generic;
3
4class MajorityElementSolver {
5 public static int MajorityElement(int[] nums) {
6 Dictionary<int, int> countMap = new Dictionary<int, int>();
7 foreach (int num in nums) {
8 if (countMap.ContainsKey(num))
9 countMap[num]++;
10 else
11 countMap[num] = 1;
12 }
13 int majorityCount = nums.Length / 2;
14 foreach (var kvp in countMap) {
15 if (kvp.Value > majorityCount) {
16 return kvp.Key;
17 }
18 }
19 return -1; // Unreachable in problem's context
20 }
21
22 static void Main() {
23 int[] nums = {2, 2, 1, 1, 1, 2, 2};
24 Console.WriteLine(MajorityElement(nums));
25 }
26}C# uses a Dictionary which automatically handles checking and updating counts in a tidy way, similar to other hash-based implementations.
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.
1public
The Java version identifies a majority element by keeping the same simple count adjustment logic as the algorithm specifies.