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/contains-duplicate/
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, trả về kết quả là true nếu bất kì phần tử nào xuất hiện hai lần trở lên, và trả về false nếu tất cả phần tử chỉ xuất hiện một lần.
Điều kiện:
1 <= nums.length <= 10^5.-10^9 <= nums[i] <= 10^9.
Bài toán minh họa 1:
Input: nums = [1,2,3,1]
Output: true
Bài toán minh họa 2:
Input: nums = [1,2,3,4]
Output: false
Bài toán minh họa 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
3. Phân tích
Ố kề, bài này quá là dễ đúng không ạ? Chúng ta có rất nhiều cách để giải quyết bài toán này.
Cách đầu tiên để giải bài toán này quá đơn giản, các bạn có thể sử dụng thuật toán Brute Force (thuật toán “trâu bò”, vét cạn) để giải quyết bài toán. Với thuật toán này thì ta sẽ làm hai cái vòng lặp for duyệt từ đầu tới cuối mảng, so sánh từng phần tử với nhau, đứa nào giống nhau thì trả về true, không thấy đứa nào giống thì trả về false.
Với cách làm này, nếu rơi vào trường hợp tệ nhất, cặp số trùng nhau xuất hiện tận cuối mảng, mà theo điều kiện đề bài, kích thước mảng có thể lên đến 10^5 phần tử, quá là nhiều, và với thuật toán này độ phức tạp sẽ là O(n^2). Không tốt một chút nào.
Cách thứ hai mà tôi nghĩ tới ấy chính là sử dụng cấu trúc dữ liệu HashMap. Với HashMap, chúng ta có thể đưa phần tử của nums vào key và số lần xuất hiện của chúng vào value của HashMap. Sau đó ta chỉ việc kiểm tra xem, có đứa nào xuất hiện hai lần trở lên thì trả về true, không có đứa nào thì trả về false. Với bài toán minh họa 1, chúng ta có:
Cách thứ ba đơn giản hơn một chút, chúng ta biết rằng mảng nums sẽ chỉ có hai trường hợp, hoặc là có phần tử lặp ít nhất hai lần, hoặc là không có phần tử nào lặp, đúng không ạ? Vậy thì tôi sẽ sử dụng HashSet để nhét tất cả phần tử của nums vào, lúc này ở trong HashSet chỉ có phần tử không trùng lặp. Để làm gì? Bây giờ chúng ta sẽ so sánh kích thước ban đầu của mảng nums và kích thước khi chỉ còn các phần tử không trùng lặp của HashSet, nếu bằng nhau thì tức là mảng nums không có phần tử nào lặp, ta trả về false, còn nếu kích thước khác nhau thì tức là có trùng lặp, ta trả ngay về true.
Và cách thứ tư, tôi sẽ nghĩ đến việc sử dụng phép so sánh XOR ^. Với cách này, đầu tiên tôi sẽ phải sắp xếp lại mảng nums theo thứ tự tăng dần bằng method sort() của class Arrays. Việc này làm cho các phần tử của mảng nums sẽ được sắp xếp theo một trật tự, và các phần tử giống nhau sẽ nằm cạnh nhau. Sau đó tôi chỉ việc sử dụng toán tử so sánh ^ với hai phần tử liền kề nhau. Hai số giống nhau mà so sánh ^ với nhau sẽ trả về kết quả là 0, ta trả kết quả về true, còn không thì là false.
Mình có mấy bài giải leetcode liên quan đến toán tử XOR này, các bạn có thể tham khảo thêm tại đây.
Done! Đến bước tiếp theo thôi.
4. Code chạy bằng cơm
4.1. Sử dụng HashMap
Đầu tiên chúng ta cần một cái HashMap với key và value đều là số nguyên Integer.
Tiếp theo, chúng ta sẽ duyệt qua mảng nums, đưa phần tử của mảng vào key của map, số lần xuất hiện của phần tử vào value. Nếu phần tử ấy chưa có trong map, ta sẽ thêm nó vào và gán cho value = 1, còn nếu nó đã xuất hiện rồi, thì vẫn phần tử ấy, nhưng value + 1:
Cuối cùng, ta duyệt qua các key có trong map bằng vòng lặp for, rồi kiểm tra xem phần tử key nào có value > 1 không? Nếu có thì trả về true, không thì false.
4.2. Sử dụng HashSet
Trước hết là phải có một cái HashSet cái đã.
Sau đó là nhét hết tất cả phần tử của nums vào trong set bằng vòng lặp for:
Khi này, trong set chỉ chứa những phần tử không trùng lặp. Ta chỉ việc đem so sánh kích thước của set với kích thước của mảng nums, nếu nó khác nhau tức là có phần tử trùng lặp, thì trả về true, còn bằng nhau thì trả về false:
4.3 Sử dụng toán tử XOR
Đầu tiên thì chúng ta sẽ sắp xếp lại mảng nums theo thứ tự tăng dần bằng method sort():
Sau đó chúng ta chỉ việc duyệt qua nums bằng vòng lặp for. Khi này, chúng ta sẽ có một biến x nhận giá trị là kết quả của phép so sánh giữa nums[i] và phần tử liền sau nó nums[i + 1]. Nếu x = 0 thì tức là hai số liền kề giống nhau, nghĩa là số đó trùng lặp, ta trả về true, còn không thì ta trả về false.
5. Code bằng máy
5.1. Sử dụng HashMap
Code sử dụng HashMap sẽ như sau:
public static boolean containsDuplicate(int[] nums) {
Map<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 : map.keySet()) {
if (map.get(i) > 1) {
return true;
}
}
return false;
}
5.2. Sử dụng HashSet
Code sử dụng HashSet sẽ như sau:
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (Integer i : nums) {
set.add(i);
}
return set.size() != nums.length;
}
5.3. Sử dụng toán tử XOR
Code sử dụng XOR sẽ như sau:
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length - 1; i++) {
int x = nums[i] ^ nums[i + 1];
if (x == 0) {
return true;
}
}
return false;
}
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!!!
Bình luận