Find the Majority Element
Easy
Given an array of integers, find the element that appears more than n/2 times where n is the size of the array. The array is guaranteed to have a majority element.
Example 1
Input
[ 3, 2, 3 ]
Output
3
Explanation. The number 3 appears 2 times which is more than `3/2`.
Example 2
Input
[ 2, 2, 1, 1, 1, 2, 2 ]
Output
2
Explanation. The number 2 appears more than `7/2` times (4 times).
Example 3
Input
[ 1 ]
Output
1
Explanation. With a single element, that element is trivially the majority element.
Example 4
Input
[ 1, 1, 2 ]
Output
1
Explanation. The number 1 appears more than `3/2` times.
Follow-up: What is the runtime complexity of your solution? Can you solve the problem in linear time?
Constraints:
The array will always be non-empty and will always contain a majority element. All array elements are integers.
- Views
- 8