You get a vector nums. One value makes up more than half of it. Return that value.
For example, in a vector of 7 numbers, that value appears at least 4 times. Every input has such a value.
Example 1:
Input: nums = [5,9,5,5,1] Output: 5 Explanation: There are 5 numbers, and 5 appears 3 times. 3 is more than half of 5.
Example 2:
Input: nums = [0,4,4,0,4,0,4,0,4] Output: 4 Explanation: 4 appears 5 times out of 9. 0 appears 4 times, which is not more than half.
Example 3:
Input: nums = [-8,2,-8,-8] Output: -8 Explanation: -8 appears 3 times out of 4. Exactly half, 2 times, would not be enough.
Constraints:
- 1 to 100,000 numbers.
- Each number is a whole number from −1,000,000,000 to 1,000,000,000.
- One value always makes up more than half of
nums.
Note:
Your solution should run in O(n log n) time.
Boyer-Moore voting is a known trick that solves it in O(n) time and O(1) space.
Cut
nums into a left half and a right half. The value you want makes up more than half of at least one of the two halves.
Find the majority of each half the same way, down to single numbers. If both halves give the same value, that is the answer. If not, count both values in the whole range and keep the one that appears more.
Each level of halving counts at most
n numbers, and there are about log n levels: O(n log n) time.The recursion is about log n calls deep, so the extra space is O(log n).
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
