30 ngày chống COVID cùng Leetcode | Ngày 07

Cho một mảng số nguyên arr, đếm số phần tử trong mảng mà x sẽ tìm thấy x +1. Đề bài có thể sẽ gây nhầm lẫn cho bạn (thực ra là tôi cũng đã  nhầm lẫn), hãy đọc kỹ các ví dụ dưới đây:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Ở ví dụ này, 1+1=2, tìm thấy 2 trong mảng, 2+1 = 3 tìm thấy 3 trong mảng.

Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.

Tương tự, nhưng ở đây không tìm thấy số nào có tính chất như vậy trong mảng.

Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.

Ở đây, cần để ý 2+1 =3, có hai số 3 trong mảng nhưng lại chỉ tính một lần, cho thấy nó không quan tâm đến các cặp x+1 giống nhau.

Input: arr = [1,1,2,2]
Output: 2
Explanation: Two 1s are counted cause 2 is in arr.

Vì có hai số 1, nên nó sẽ thỏa mãn 2 cặp 1+1=2, 1+1=2, đừng để bị lừa vì có 2 chữ số 2, như đã xét ở ví dụ trên x+1 có bao nhiêu số cũng không quan trọng.

Khi đã hiểu kỹ đề bài, ta có thể đưa ra giải pháp có độ phức tạp O(n) thời gian và O(n) không gian. Ta sẽ có một cấu trúc dữ liệu để lưu lại các số không trùng nhau, tôi dùng Set. Nếu implement bằng Python thì chắc sẽ hay hơn. Còn mảng thì không khả thi nếu số lượng lớn.

Khi duyệt phần tử chạy trên mảng Arr, tôi sẽ xem xét xem Arr[i]+1 có tồn tại trong Set không, nếu có thì tăng count++.

Còn đây là code Java:


Hết rồi, hẹn gặp Leetcode vào ngày mai. Cảm ơn bạn !