18. Majority Element

Easy · Array

Given an array of integers, find the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times, where n is the length of the array. You may assume that the majority element always exists in the input.

The majority element is guaranteed to exist, so you do not need to handle cases where no element appears more than n/2 times.

Examples

Example 1
Input: [3, 2, 3]
Output: 3
Explanation: The element 3 appears 2 times, which is more than ⌊3 / 2⌋ = 1 time. So 3 is the majority element.
Example 2
Input: [2, 2, 1, 1, 1, 2, 2]
Output: 2
Explanation: The element 2 appears 4 times, which is more than ⌊7 / 2⌋ = 3 times. So 2 is the majority element.

Constraints