Cùng giải leetcode! Bài 169. Majority Element

Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/majority-element/

1. Mở đầu

Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.

2. Đề bài

Cho một mảng số nguyên nums với kích thước n, trả về phần tử đa số (có số lần xuất hiện nhiều nhất).
Phần tử đa số là phần tử có số lần xuất hiện lớn hơn [n/2] lần. Luôn có phần tử đa số xuất hiện ở trong mảng.

Điều kiện:

n == nums.length.
1 <= n <= 5 * 10^4.
-10^9 <= nums[i] <= 10^9.

Ví dụ 1:

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

Ví dụ 2:

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

3. Phân tích

Âu kê, bài này yêu cầu chúng ta tìm ra phần tử đa số trong một mảng số nguyên nums. Phần tử đa số là phần tử có số lần xuất hiện lớn hơn [n/2] lần. Vậy đây sẽ là mốc để chúng ta thực hiện kiểm tra xem phần tử nào vượt qua mốc [n/2] này thì trả về phần tử đó.
Để giải quyết bài toán này chúng ta sẽ có hai cách để giải:

Cách 1: Sử dụng thuật toán Brute Force (thuật toán vét cạn)
Chúng ta sẽ kiểm tra lần lượt từng phần tử trong nums, cần có hai vòng lặp để kiểm tra phần tử hiện tại với các phần tử còn lại. Nếu hai phần tử bằng nhau, thì chúng ta đếm số lần xuất hiện của phần tử (tạm gọi là count) đó thêm 1. Sau khi kiểm tra xong phần tử đó, chúng ta so sánh count với [n/2], nếu count > [n/2] thì trả về phần tử đó, nếu không thì ta kiểm tra phần tử khác.
Ưu điểm của cách này là chúng ta giải được bài toán, nhược điểm của cách này thì như mình nói ở các bài trước, thời gian chạy có khả năng sẽ lâu tùy thuộc vào kích thước mảng nums, thêm nữa là chúng ta sẽ phải kiểm tra cả những trường hợp không cần thiết. Vậy nên chúng ta hướng tới cách 2.
Cách 2: Sắp xếp rồi tìm ra phần tử đa số
Chúng ta sẽ sắp xếp lại mảng nums theo thứ tự tăng dần hoặc giảm dần. Dù là tăng dần hay tăng dần, phần tử đa số sẽ luôn xuất hiện ở vị trí [n/2].
Chúng ta sẽ làm rõ hơn ở phần tiếp theo.

4. Code chạy bằng cơm

4.1. Sử dụng Brute Force

Hãy thử với ví dụ 2 với nums = [2,2,1,1,1,2,2]. Ta có một vòng lặp ngoài với con trỏ i để kiểm tra phần tử hiện tại, và một vòng lặp trong với con trỏ j để so sánh với phần tử ở vòng lặp ngoài:
leetcode-169-1

Giờ ta cứ lần lượt kiểm tra i = j hay không, ta có một biến là count để đếm số lần xuất hiện của i, nếu i = j thì count tăng thêm 1:
leetcode-169-2

Sau khi j chạy hết mảng, ta sẽ có số lần xuất hiện count = 4, ta so sánh count với n:
leetcode-169-3

Vậy 2 là phần tử đa số của mảng nums.

4.2. Sử dụng sorting

Với cách này chúng ta sẽ bám sát vào khái niệm của phần tử đa số, ấy là phần tử đa số là phần tử có số lần xuất hiện lớn hơn [n/2] lần. Vậy nếu chúng ta sắp xếp lại mảng nums theo thứ tự nhất định, là tăng dần hoặc giảm dần, thì phần tử đa số sẽ luôn nằm ở vị trí index [n/2]. Hãy nhìn vào ví dụ 2 sau khi sắp xếp, các bạn sẽ hiểu ý tôi nói:
leetcode-169-4

5. Code chạy bằng máy

5.1. Sử dụng Brute Force

Code của chúng ta như sau:

 public int majorityElement(int[] nums) {
     int m = nums.length/2;

     for (int i : nums) {
         int count = 0;
         for (int j : nums) {
             if (i == j) {
                 count += 1;
             }
         }

         if (count > m) {
             return num;
         }

     }

     return -1;    
 }

5.2. Sử dụng Sorting