Find the Majority Element

ArrayCountingHash Table

Given an array of integers, find the element that appears more than n/2 times where n is the size of the array. Assume that there is always such a majority element and the array is non-empty.

Example 1

Input

[
  3,
  3,
  4,
  2,
  4,
  4,
  2,
  4,
  4
]

Output

Explanation. The number 4 appears 5 times while the size of the array is 9 which is greater than 9/2.

Example 2

Input

[
  1
]

Output

Explanation. The number 1 appears once in the array of size 1, which is more than 1/2.

Example 3

Input

[
  1,
  2,
  1
]

Output

Explanation. The number 1 appears twice in an array of 3 elements, which matches the condition of appearing more than 3/2 times.

Follow-up: Can you solve the problem in O(n) time and O(1) extra space?

Constraints:

- The array is guaranteed to have a majority element.\n- Array size will at least be 1.

Views: 3