Majority Element
EasyArray · Adobe
You are given an integer array nums of length n. Its majority element is the value that appears more than n / 2 times, so it occupies more than half of all positions. Every input is guaranteed to have one.
Return the majority element.
Follow-up: can you solve it in O(n) time while using only O(1) extra space?
Example 1
- Input:
- nums = [-4,7,-4,7,-4,7,-4]
- Output:
- -4
- Explanation
- -4 appears 4 times out of 7, which is more than 7 / 2 = 3.5. 7 appears only 3 times, so it does not qualify even though it is close.
Example 2
- Input:
- nums = [6,1,6,6,2]
- Output:
- 6
- Explanation
- 6 fills 3 of the 5 positions, more than half.
Example 3
- Input:
- nums = [5,9,9]
- Output:
- 9
- Explanation
- 9 appears twice out of 3. The majority does not have to be the first value.
Constraints
n == nums.length1 <= n <= 5 * 10^4-10^9 <= nums[i] <= 10^9- A majority element always exists