Find Majority Element

ArrayCountingHash Table

Given an array of integers, find the majority element. The majority element is the element that appears more than ( n/2 ) times, where ( n ) is the number of elements in the array.

Example 1

Input

[
  3,
  2,
  3
]

Output

Explanation. The element '3' appears 2 times which is more than \( 3/2 \).

Example 2

Input

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

Output

Explanation. The element '2' appears 4 times which is more than \( 7/2 \).

Example 3

Input

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

Output

Explanation. The element '1' appears 4 times which is more than \( 7/2 \).

Follow-up: Can you solve the problem in linear time and constant space complexity?

Constraints:

The input array is guaranteed to always contain a majority element.

Views: 1