169. Majority Element
Tags:
Easy
Skills:
Boyer Moore
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm phẩn tử xuất hiện nhiều hơn n/2 lần trong mảng nums (giả sử luôn tồn lại phần tử như vậy)
Approach - Boyer Moore voting algorithm
Duyệt qua mảng, chọn một candidate và count. Nếu count về 0, chọn phần tử hiện tại làm candidate mới. Nếu phần tử hiện tại trùng candidate, tăng count, ngược lại giảm count. Kết thúc, candidate chính là majority element
Solution
1function majorityElement(nums: number[]): number {
2 let count = 0;
3 let candidate = nums[0];
4 for (let i = 0; i < nums.length; i++) {
5 if (count === 0) {
6 candidate = nums[i]
7 }
8 count += (nums[i] === candidate) ? 1 : -1;
9 }
10
11 return candidate
12};