tom007
BAN USERHere's an algorithm with O(n) time and O(1) space. Have one variable keep track of current member and another variable keep track of the counter:
1. Initially current member is the first member and counter is 1.
2. introduce the next member to current member. If they belong to the same party then increment the counter of current member; otherwise decrement the counter. If the counter becomes 0 then replace the current member with the next member and set its counter to 1.
3. repeat step 2 until either counter exceeded majority half or all members have been introduced. The current member remaining is the majority member.
The idea is to get rid off each minority member by pairing it up with either a majority member or another minority member. For example, say there are 9 total members of 5 majority and 4 minority, in the worst case, the order of introduction results in 4 minority cancel out with 4 majority, there is still one majority left to give the correct result.
Assuming the minimal subset contains m numbers. We can do:
1. put all numbers in an array and compute the total sum along the way - O(n).
2. heapify the array (use min heap) - O(n)
3. start removing min from root as long as the total sum is still >= k - O((n-m)*logn)
Above will work well if m is close to n, i.e. it takes most of the numbers to sum up to k.
If it's the opposite case, i.e. it only takes few numbers to sum up to k, then we can try a different approach:
1. insert array elements into min heap until the sum of heap is >=k.
2. remove min from root as long as remaining sum is >=k.
3. scan the remaining array elements. If bigger than heap root than add it to the heap.
4. repeat step 2.
Above will take O(n*logm) where m is heap size. Since the assumption is that m is small, it'll be better than O(n*logn).
Sort the array with a new comparator that when comparing two integers, concat them as strings in different order before comparing. For example, compare 9 and 91 becomes comparing "991" and "919" and thus 9 is great than 91. Java code below:
- tom007 April 14, 2012