Arrays & Hashing
LC #169Easy
Majority Element
Arrays & Hashing
Problem
Given an array nums of size n, return the majority element (appears more than ⌊n / 2⌋ times). Must solve in O(n) time and O(1) space.
arraydivide-and-conquervoting
Constraints
- ›n == nums.length
- ›1 ≤ n ≤ 5 * 10⁴
- ›-10⁹ ≤ nums[i] ≤ 10⁹
Example
Input
nums = [2, 2, 1, 1, 1, 2, 2]Output
2Why
2 appears 4 times, which is more than ⌊7/2⌋ = 3.