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. The array is guaranteed to have a majority element.

Example 1

Input

[
  3,
  2,
  3
]

Output

Explanation. The number 3 appears 2 times which is more than `3/2`.

Example 2

Input

[
  2,
  2,
  1,
  1,
  1,
  2,
  2
]

Output

Explanation. The number 2 appears more than `7/2` times (4 times).

Example 3

Input

[
  1
]

Output

Explanation. With a single element, that element is trivially the majority element.

Example 4

Input

[
  1,
  1,
  2
]

Output

Explanation. The number 1 appears more than `3/2` times.

Follow-up: What is the runtime complexity of your solution? Can you solve the problem in linear time?

Constraints:

The array will always be non-empty and will always contain a majority element. All array elements are integers.

Views: 2