Sponsored
Sponsored
This approach leverages a hashmap to count the occurrences of each element in the input array. We iterate through the array once to populate the hashmap and then make another pass to find all elements whose count is greater than ⌊n/3⌋. While this method is straightforward and simple to implement, it uses extra space proportional to the number of unique elements.
Time Complexity: O(n), where n is the length of the array since we go through the list of numbers twice.
Space Complexity: O(n) to handle the possible maximum unique elements.
1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5// Define a simple hash map structure
6typedef struct {
7 int key;
8 int count;
9} Element;
10
11Element* createMap(int size) {
12 Element *elements = (Element*) malloc(size * sizeof(Element));
13 for (int i = 0; i < size; i++) {
14 elements[i].key = INT_MIN;
15 elements[i].count = 0;
16 }
17 return elements;
18}
19
20void addItem(Element* map, int size, int num) {
21 for (int i = 0; i < size; i++) {
22 if (map[i].key == num || map[i].key == INT_MIN) {
23 if (map[i].key == INT_MIN) map[i].key = num;
24 map[i].count++;
25 return;
26 }
27 }
28}
29
30int* majorityElement(int* nums, int numsSize, int* returnSize) {
31 int limit = numsSize / 3;
32 Element* countMap = createMap(numsSize);
33 for (int i = 0; i < numsSize; i++) {
34 addItem(countMap, numsSize, nums[i]);
35 }
36
37 int *result = (int*) malloc(numsSize * sizeof(int));
38 *returnSize = 0;
39 for (int i = 0; i < numsSize; i++) {
40 if (countMap[i].key != INT_MIN && countMap[i].count > limit) {
41 result[*returnSize] = countMap[i].key;
42 (*returnSize)++;
43 }
44 }
45
46 free(countMap);
47 return result;
48}
49
50int main() {
51 int nums[] = {3,2,3};
52 int returnSize;
53 int* result = majorityElement(nums, 3, &returnSize);
54 for (int i = 0; i < returnSize; i++) {
55 printf("%d ", result[i]);
56 }
57 free(result);
58 return 0;
59}The provided C code creates a custom hashmap-like structure to count elements. This hashmap uses an array of structs where each struct holds a key-value pair corresponding to a number and its count. We iterate over the input array to update the counts, and finally check which numbers exceed the ⌊n/3⌋ threshold. Note that handling collisions could be optimized further.
The Boyer-Moore Voting Algorithm is optimized for finding the majority element which appears more than n/2 times. Here, we extend it to handle the case for n/3 by maintaining up to two potential candidates, since at most two elements can qualify for appearing more than ⌊n/3⌋ times. In the first pass, we identify the element candidates by attempting to cancel them out against others. A second pass is required to confirm the counts of these candidates to ensure they appear more than ⌊n/3⌋ times.
Time Complexity: O(n), going through elements twice.
Space Complexity: O(1) as no additional space is needed apart from variables.
using System.Collections.Generic;
public class Solution {
public IList<int> MajorityElement(int[] nums) {
int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;
foreach (int num in nums) {
if (num == candidate1) {
count1++;
} else if (num == candidate2) {
count2++;
} else if (count1 == 0) {
candidate1 = num;
count1 = 1;
} else if (count2 == 0) {
candidate2 = num;
count2 = 1;
} else {
count1--;
count2--;
}
}
count1 = count2 = 0;
foreach (int num in nums) {
if (num == candidate1) {
count1++;
} else if (num == candidate2) {
count2++;
}
}
IList<int> result = new List<int>();
if (count1 > nums.Length / 3) {
result.Add(candidate1);
}
if (count2 > nums.Length / 3) {
result.Add(candidate2);
}
return result;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {3, 2, 3};
IList<int> result = sol.MajorityElement(nums);
foreach (int num in result) {
Console.Write(num + " ");
}
}
}This C# program implements Boyer-Moore logic maintaining two potential lead candidates by balancing count cycles, verifying them afterward to ensure genuine majority status.