Find Majority Element

ArrayCountingHash Table

Given an array of size 'n', find the element that appears more than n/2 times. This element is known as the majority element. Assume that there always exists a majority element.

Example 1

Input

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

Output

Explanation. The element 4 appears 5 times which is more than half of the array size (9/2 = 4.5).

Example 2

Input

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

Output

Explanation. The element 1 appears 4 times which is more than half of the array size (7/2 = 3.5).

Example 3

Input

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

Output

Explanation. The element 2 appears 4 times which is more than half of the array size (7/2 = 3.5).

Follow-up: How might the solution change if we relaxed the requirement of always having a majority element?

Constraints:

- The array will always have a majority element. - Each element in the array is a non-negative integer. - The array size, n, is at least 1.

Views: 2