169. Majority Element

🔗 Link bài toán: Majority Element

🔺 Mô tả bài toán:
Cho một mảng số nguyên nums có kích thước n, hãy tìm phần tử xuất hiện nhiều hơn ⌊n / 2⌋ lần. Bạn có thể giả định rằng luôn tồn tại một phần tử như vậy.

💡 Ý tưởng:
Bài toán này có thể được giải quyết hiệu quả bằng thuật toán Boyer-Moore Voting Algorithm.

• Chúng ta giả định một phần tử làm ứng viên (candidate) và sử dụng một biến count để theo dõi số lần xuất hiện của nó.

• Duyệt qua mảng:

  • Nếu phần tử hiện tại trùng với candida``te, tăng count.

  • Nếu không, giảm count.

  • Khi count giảm về 0, cập nhật candidat``e thành phần tử hiện tại và đặt lại count = 1.

• Do luôn tồn tại phần tử chiếm đa số, cuối cùng candidate sẽ là đáp án đúng.

🔧 Solution: https://leetcode.com/problems/majority-element/solutions/6491313/easy-solution-with-java-by-thanhdt942-tug5/

⏱️ Độ phức tạp:

• Time complexity: O(n) - Duyệt qua mảng một lần.

• Space complexity: O(1) - Không sử dụng bộ nhớ bổ sung.