Majority Element
Description: Given array nums of length n, find the majority element — the one appearing more than n/2 times. It is guaranteed to exist.
Example 1:
Input: nums = [3,2,3]
Output: 3
Explanation: Three appears 2 times out of 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
Explanation: Two appears 4 times out of 7
Constraints:
1 <= nums.length <= 5·10⁴
Элемент большинства гарантированно существует
Recommended time and space complexity
Aim for O(n) time and **O(1) space**.
Hint 1
A frequency table costs O(n) space. The constraint asks for O(1).
Hint 2
Imagine different elements cancelling each other out.
Hint 3
Keep a candidate and a counter: match increments, mismatch decrements, zero picks a new candidate.