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.
1using System;
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.