446. Find N/3 Majority Element Using Binary Search

Given an integer array nums, return the element that appears more than ⌊n/3⌋ times. It is guaranteed that such an element exists. If multiple majority elements exist, return the smallest one. Solve using binary search on sorted array.

Input: An integer array nums (guaranteed to have at least one majority element).

Output: The smallest element appearing more than n/3 times.

Examples

Input: [3,2,3]
Output: 3
Explanation: 3 appears 2 times > 3/3=1. Majority is 3.

Input: [1,2,1,2,3,1]
Output: 1
Explanation: 1 appears 3 times > 6/3=2. Majority is 1.

Input: [5,5,5,5,1,2,3,4]
Output: 5
Explanation: 5 appears 4 times > 8/3=2.6. Majority is 5.

Constraints

• 1 <= nums.length <= 5*10^4
• At least one element appears > n/3 times
• -10^9 <= nums[i] <= 10^9

Asked by