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.
1def majorityElement(nums):
2 counts = {}
3 for num in nums:
4 if num in counts:
5 counts[num] += 1
6 else:
7 counts[num] = 1
8 for num, count in counts.items():
9 if count > len(nums) // 2:
10 return num
11
12print(majorityElement([2, 2, 1, 1, 1, 2, 2]))Python utilizes a dictionary for counting, and then iterates through the dictionary to retrieve the majority element by scanning through its counts.
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
class MajorityElementSolver {
public static int MajorityElement(int[] nums) {
int count = 0, candidate = 0;
foreach (int num in nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
static void Main() {
int[] nums = {2, 2, 1, 1, 1, 2, 2};
Console.WriteLine(MajorityElement(nums));
}
}C# uses the Boyer-Moore algorithm to simplify the operation of ensuring majority element finding in a controlled pass through the array.