Arrays and Hashing Counting and voting
68. Majority Element
You are given an array of integers nums of length n. One value in it is the majority value: it
appears more than n / 2 times. Return that value.
"More than n / 2 times" means strictly more than half. In an array of 6 elements the majority value
appears at least 4 times, and in an array of 7 elements at least 4 times.
Example 1
Input: nums = [3, 8, 3, 3, 5, 3, 8]
3Explanation: 3 appears 4 times out of 7, which is more than half. 8 appears twice and 5 once.
Example 2
Input: nums = [-4]
-4Explanation: The only element appears once out of 1, which is more than half.
Example 3
Input: nums = [9, -2, -2, 9, -2]
-2Explanation: −2 appears 3 times out of 5. 9 appears twice, which is less than half of 5.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 109- One value appears more than
n / 2times.
Clarifying questions
What you would ask an interviewer before writing any code.