Given an array nums of size n, return the majority element: the value that appears more than n / 2 times. The array always has one.
Can you do it in O(n) time and O(1) extra space?
Examples
Example 1
- Input
- nums = [3, 2, 3]
- Output
- 3
Example 2
- Input
- nums = [2, 2, 1, 1, 1, 2, 2]
- Output
- 2
Constraints
1 <= nums.length <= 5 * 10^4-10^9 <= nums[i] <= 10^9