Find Majority Element

ArrayCountingHash Table

Given an array of integers, find the element that appears more than n/2 times in the array, where n is the array's length. The array is guaranteed to have a majority element. Return the majority element.

Example 1

Input

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

Output

Explanation. 4 appears 5 times in an array of 9 elements, which is more than 9/2 times.

Example 2

Input

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

Output

Explanation. 1 appears 4 times in an array of 7 elements, which is more than 7/2 times.

Example 3

Input

[
  6,
  6,
  6,
  7,
  7
]

Output

Explanation. 6 appears 3 times in an array of 5 elements, which is more than 5/2 times.

Follow-up: What would be the optimal way to find the majority element in terms of space and time complexity?

Constraints:

The input array will contain at least one integer and all elements are integers. The array is guaranteed to have a majority element which appears more than `n/2` times.

Views: 4