55
The majority element (if it exists) will also be the median. We can find the median in O(n) and then check that it is indeed a valid majority element in O(n). More details for implementation link
Majority Element:
A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).
Finding a Candidate:
The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.
findCandidate(a[], size)
1. Initialize index and count of majority element
maj_index = 0, count = 1
2. Loop for i = 1 to size – 1
(a)If a[maj_index] == a[i]
count++
(b)Else
count--;
(c)If count == 0
maj_index = i;
count = 1
3. Return a[maj_index]
Above algorithm loops through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1. First Phase algorithm gives us a candidate element. In second phase we need to check if the candidate is really a majority element.
Second phase is simple and can be easily done in O(n). We just need to check if count of the candidate element is greater than n/2.
Read geeksforgeeks for more details
If you are allowed to create a hash-table and assume hash-entry lookup is constant you just hash_map each entry against the number of occurrences.
You could do a second pass through the table you get the one with the highest count, but if you know in advance the number of elements in the table, you will know immediately if we have a majority element on the first pass when we hit the required count on the element.
You cannot guarantee of course that there is even a sequence of 2 consecutive occurrences of the element eg 1010101010101010101 has no consecutive 1s but it is a majority element.
We are not told anything about whether there is any kind of ordering on the element type although obviously we must be able to compare two for equality.
Sort the given array : O(nlogn).
If the array size is 7, then the majority element occurs atleast ceiling(7/2) = 4 times in the array.
After the array is sorted, it means that if the majority element is first found at position i, it is also found at position i + floor(7/2) (4 occurences).
Example - Given array A - {7,3,2,3,3,6,3}
Sort the array - {2,3,3,3,3,6,7}
The element 3 is found at position 1 (array index starting from 0.) If the position 1 + 3 = 4th element is also 3, then it means 3 is the majority element.
if we loop through the array from beginning..
compare position 0 with position 3, different elements 2 and 3. compare position 1 with position 4, same element. We found our majority match!
Complexity - O(n)
Total time complexity - O(n).