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 <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5int majorityElement(int* nums, int numsSize) {
6 int *hashTable = (int*)calloc(2000000000, sizeof(int)); // Very large to accommodate range
7 int offset = 1000000000; // Offset for negative numbers
8 for (int i = 0; i < numsSize; i++) {
9 hashTable[nums[i] + offset]++;
10 }
11 for (int i = 0; i < numsSize; i++) {
12 if (hashTable[nums[i] + offset] > numsSize/2) {
13 free(hashTable);
14 return nums[i];
15 }
16 }
17 free(hashTable);
18 return -1;
19}
20
21int main() {
22 int nums[] = {2, 2, 1, 1, 1, 2, 2};
23 int size = sizeof(nums)/sizeof(nums[0]);
24 printf("%d", majorityElement(nums, size));
25 return 0;
26}In C, we use a large-sized array as a hash table since specific implementations of dynamic hashmap are not readily available. We loop through the array to populate this table and again to check for the majority element. This approach uses the offset to handle negative numbers.
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.