Cùng giải leetcode! Bài 136. Single Number

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/single-number/

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 có ít nhất một phần tử, tất cả các phần tử trong đó đều sẽ xuất hiện hai lần, ngoại trừ một phần tử chỉ xuất hiện một lần duy nhất. Hãy tìm phần tử đó.

Bạn phải triển khai một giải pháp có độ phức tạp thời gian chạy tuyến tính và chỉ sử dụng không gian bổ sung không đổi.

Điều kiện:

• 1 <= nums.length <= 3 * 104.
• -3 * 104 <= nums[i] <= 3 * 104.
• Tất cả các phần tử trong mảng đều xuất hiện hai lần, ngoại trừ một phần tử chỉ xuất hiện duy nhất một lần.

Ví dụ 1:

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

Ví dụ 2:

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

Ví dụ 3:

Input: nums = [1]
Output: 1

3. Phân tích

Ok bài này cũng không quá khó đâu các bạn ạ. Chúng ta chỉ cần tìm phần tử xuất hiện một lần duy nhất trong mảng, hãy để ý đến điều kiện của bài toán, kích thước của mảng có thể là 1, vậy thì ngay câu lệnh đầu chúng ta sẽ kiểm tra xem kích thước của mảng có bằng 1 hay không? Nếu có thì trả về luôn phần tử duy nhất đó.
Bài này sẽ có hai cách giải, cách đầu tiên chúng ta sẽ làm theo kiểu “miễn là ra được đáp án”; cách thứ hai chúng ta sẽ đáp ứng yêu cầu của đề bài, ấy là phải triển khai một giải pháp có độ phức tạp thời gian chạy tuyến tính và chỉ sử dụng không gian bổ sung không đổi.

• Cách 1:
  Chúng ta sẽ sử dụng cấu trúc dữ liểu HashMap, với key là phần tử của mảng num và value là số lần xuất hiện của nó. Sau đó ta kiểm tra xem phần tử nào xuất hiện một lần duy nhất thì ta trả về phần tử đó.
• Cách 2:
  Yêu cầu của đề bài là chúng ta phải có một giải pháp với độ phức tạp thời gian chạy tuyến tính và chỉ sử dụng không gian bổ sung không đổi. Có nghĩa là chúng ta không được sử dụng cấu trúc dữ liệu bảng băm (như HashSet hay HashMap). Thay vào đó chúng ta sẽ sử dụng phép so sánh XOR để loại đi những phần tử trùng nhau. Vậy chúng ta chỉ cần đặt phép so sánh cho tất cả các phần tử có trong nums, số nào trùng thì chúng sẽ có kết quả là 0, số nào xuất hiện một lần thì khi so sánh XOR với 0 sẽ bằng chính nó. Với cách này, chúng ta đã đáp ứng được yêu cầu đề bài đưa ra.

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

4.1. Sử dụng HashMap

Với cách sử dụng HashMap, chúng ta sẽ duyệt qua mảng nums, rồi gán phần tử của nums vào map. Nếu chưa xuất hiện thì thêm vào map, đồng thời gán value = 1, còn nếu xuất hiện rồi thì value + 1.
Tại i = 4, chưa xuất hiện nên ta gán nó vào key, và value của nó là 1:

Tại i = 1, cũng chưa xuất hiện nên ta làm như trên:

Tại i = 2 cũng thế:

Nhưng khi i = 1, lần này nó đã có trong map rồi, nên ta tăng value + 1:

Và cuối cùng tại i = 2 cũng thêm value + 1:

Kiểm tra trong map thấy số 4 có value = 1, vậy thì suy ra 4 là số ta cần tìm:

4.2. Sử dụng XOR

Chúng ta sẽ cho toàn bộ các phần tử trong nums thực hiện phép so sánh XOR một cách tuần tự từ đầu đến cuối. Như tôi đã giải thích ở trên, cứ hai số giống nhau thì khi so sánh XOR với nhau sẽ có kết quả bằng 0, số xuất hiện một lần sẽ lộ ra:

Thực chất code sẽ chạy như thế này, ở vòng lặp đầu tiên sẽ thực hiện phép so sánh 4 ^ 1:

Tại vòng lặp tiếp theo sẽ thực hiện so sánh kết quả vừa tìm được với phần tử kế tiếp là 2:

Tiếp theo với phần tử 1:

Và phần tử cuối cùng là 2:

Kết quả cuối cùng vẫn là 4, tức là số chỉ xuất hiện một lần. Done!

5. Code bằng máy

5.1. Sử dụng HashMap

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

 public int singleNumber(int[] nums) {
     if (nums.length == 1) {
         return nums[0];
     }

     HashMap<Integer, Integer> map = new HashMap<>();

     for (int i : nums) {
         if (!map.containsKey(i)) {
             map.put(i, 1);
         } else{
             map.put(i, map.get(i) + 1);
         }
     }

     for (int i : nums) {
         if (map.get(i) == 1) {
             return i;
         }
     }

     return 0;
 }

5.2. Sử dụng XOR

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

 public static int singleNumber(int[] nums) {
     if (nums.length == 1) {
         return nums[0];
     }
     int ans = 0;

     for (int i : nums) {
         ans ^= i;
     }

     return ans;
 }

6. Kết thúc

Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!