Maychallengen (36) | Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

Bài này có thể hoàn thành với time O(N) và space O(N) sử dụng map. Hoặc chỉ space O(1) với thuật toán Boyer-Moore Voting .

Gọi biến candicate (ứng viên ) là số majority tính đến thời điểm hiện tại, count là biến đếm tăng lên khi số đang duyệt bằng candicate và giảm trong các trường hợp còn lại.

• Initialize an element m and a counter i with i = 0
• For each element x of the input sequence:
  • If i = 0, then assign m = x and i = 1
  • else if m = x, then assign i = i + 1
  • else assign i = i − 1
• Return m

.
Cảm ơn bạn ! À mình bổ sung thêm một chút là thuật toán Boyer-Moore chỉ áp dụng cho trường hợp luôn tồn tại Majority Element thôi nhé.