Given a list of integers, we would like to find the majority element. The majority element is the number that is repeated more than half of the size of the given array.
Examples:
Let A = { 3,5,3,5,3,7,3,9,3 } Ans: 3 since 3 occurred more than half of this array.
Solution:
Method 1
We can easily solve this with the power of hashtable. First we store the count of each integer as a value for a hashtable with key of the integer.
Then we come back and iterate through the keys of the hashtable and we check if any of them are greater than half of the count of the array
if (nums.Length == 0)
return -1;
Hashtable ht = new Hashtable();
for (int i = 0; i < nums.Length; i++) {
if (!ht.ContainsKey(nums[i])) {
ht.Add(nums[i], 1);
}
else {
ht[nums[i]] = (int)ht[nums[i]] + 1;
}
}
foreach (int i in ht.Keys) {
if ((int)ht[i] > nums.Length / 2)
return i;
}
return 0;
Method 2
We can also calculate the majority element in each iteration as follows:
- If our count of current candidate number goes to zero , we will update our majority element to the current item in the list.
- Else check if current item is same as our candidate and if so, we will increment count by 1
- otherwise decrement count by one
- Finally the real count of our candidate by running a new loop and see if that is more than half of the items.
Note: The key thing in this algorithm is that for a number to be a majority number it shall be present in the array at least every other number including boundary values. Therefore as long as there is chance I can see the candidate after another number, I won't change my majority candidate number. Otherwise I have to update my majority number and keep checking the same way.
int count =0 ;
int majority = 0;
for (int i = 0; i < a.Length; i++) {
if (count == 0) {
majority = a[i];
count = 1;
}
else if (a[i] == majority)
count++;
else
count--;
}
count = 0;
for (int i = 0; i < a.Length; i++) {
if (a[i] == majority)
count++;
}
if (count > a.Length / 2)
return majority;
else
return 0;