Find the majority number in a given sequence of numbers (a number that occurs more than N/2 times where N is the count of numbers in the sequence). Don't maintain a map of all occurring numbers along with a count. No number may be a majority.
Example: 1 1 2 3 4 1 6 1 7 1 1
Majority number is 1 since it occurs 6 times (> 11/2)
Solution:
maintain a counter and store the current number. If next number is same increment the counter, if different then decrement counter. If counter becomes zero, then store the next number as current number and set counter to 1, like a fresh start. After itertation is done, you will be left with a current number. Traverse the array once more to check if it is really majority or not. O(n) complexity.
(Moore voting algorithm).
Complexity:
time - O(n)Links and credits:
space - O(1)
http://www.careercup.com/question?id=5200260502650880
http://www.cs.utexas.edu/~moore/best-ideas/mjrty/
Another Algo (inspired by chip testing in Cormen book), pair elements like (first, second), (third, fourth) ... and so..on, if pair has same elements, keep one of the element, else discard that pair. You will always be left with most occurring number. eg : 5,1,1,2,1,4,1,1 => Pairs : (5,1) - discarded, (1,2) - discarded, (1,4) - discarded, (1,1) - 1 taken. So, 1 is the solution. Lets take another example, this time with odd number of elements, if number of elements are odd, last one will be left out, and if all other pairs get discarded, then the last one is the solution, eg : 5,1,1,2,1,4,1,9,1 => Pairs : (5,1) - discarded, (1,2) - discarded, (1,4) - discarded, (1,9) - discarded, 1 is left and none of the pairs were accepted, so, 1 is the solution. Hope this helps someone :)
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThanks for the comment. If we consider the last case (odd number of elements) and replace the very last 1 with, say, 9, then your algorithm will still return the last element of the sequence - that is 9. And this is incorrect.
ReplyDelete