Contains Duplicate

Q: So sánh kích thước của tập hợp với độ dài của mảng có phải là một lời giải hợp lệ không?

Có. Tạo một tập hợp từ toàn bộ nums rồi kiểm tra xem nó có nhỏ hơn mảng hay không. Cách này chạy trong thời gian O(n) và dùng O(n) bộ nhớ.

DễBăm

+10

Bạn được cung cấp một mảng số nguyên nums. Trả về true nếu có giá trị nào xuất hiện ít nhất hai lần trong mảng, và false nếu mọi giá trị đều khác nhau.

Hàm

containsDuplicate(nums: integer-array) → boolean

numsinteger-array: các số nguyên cần kiểm tra
Trả vềboolean: true nếu một giá trị xuất hiện ít nhất hai lần, false nếu không

Ràng buộc

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹

Ví dụ

Đầu vào: nums = [3, 1, 4, 1, 5]
Đầu ra: true
Giải thích: Giá trị 1 xuất hiện ở chỉ số 1 và một lần nữa ở chỉ số 3, vì vậy đáp án là true.

Đầu vào: nums = [2, 7, 1, 8]
Đầu ra: false
Giải thích: 2, 7, 1 và 8 là bốn giá trị khác nhau, nên không có giá trị nào lặp lại.

Đầu vào: nums = [-4, 4, 0]
Đầu ra: false
Giải thích: -4 và 4 có cùng giá trị tuyệt đối nhưng là hai số khác nhau, còn 0 chỉ xuất hiện một lần, nên đáp án là false.

Câu hỏi mở rộng

Bạn có thể dừng ngay khi gặp giá trị lặp lại đầu tiên, thay vì luôn đọc hết mảng không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Một giá trị lặp lại là giá trị bạn đã gặp trước đó, nên việc cần làm là nhanh chóng trả lời câu hỏi “mình đã gặp giá trị này chưa?”. So sánh từng cặp cần khoảng 5 × 10^7 phép so sánh khi n = 10^4. Sắp xếp đưa các giá trị bằng nhau về cạnh nhau, còn tập hợp băm trả lời câu hỏi trong thời gian trung bình O(1), nhờ đó chỉ cần duyệt một lượt.

Sắp xếp, rồi so sánh các phần tử liền kề

Ý tưởng

Trong một mảng đã sắp xếp, các giá trị bằng nhau nằm cạnh nhau: [3, 1, 4, 1, 5] được sắp xếp thành [1, 1, 3, 4, 5], và hai số 1 nằm cạnh nhau. Vì vậy, sau khi sắp xếp, bạn chỉ cần so sánh mỗi giá trị với giá trị đứng ngay trước nó, tổng cộng n-1 lần so sánh.

Nếu không có hai phần tử liền kề nào bằng nhau thì không có hai giá trị nào ở bất kỳ vị trí nào bằng nhau: mọi giá trị nằm giữa hai bản sao của x theo thứ tự đã sắp xếp đều vừa lớn hơn hoặc bằng x, vừa nhỏ hơn hoặc bằng x, nên nó cũng phải là một x khác.

Chi phí của bước sắp xếp chi phối thời gian chạy, ở mức O(n log n). Sắp xếp tại chỗ không cần thêm mảng nhưng sẽ sắp xếp lại đầu vào của bên gọi; sắp xếp một bản sao tốn O(n) dung lượng.

Thuật toán

Sắp xếp nums theo thứ tự tăng dần.
Lặp i từ 1 đến chỉ số cuối cùng.
Nếu nums[i] bằng nums[i-1], trả về true.
Sau vòng lặp, trả về false.

def containsDuplicate(nums):
    nums.sort()
    # After sorting, equal values sit next to each other.
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            return True
    return False

Một lượt duyệt với tập hợp băm

Ý tưởng

Duyệt qua mảng một lần và lưu mọi giá trị bạn đã đi qua trong một tập hợp băm. Tập hợp luôn chứa chính xác các giá trị nằm trước vị trí hiện tại, vì vậy nếu tìm thấy giá trị trùng thì giá trị hiện tại đã xuất hiện trước đó, còn nếu đi đến cuối mà không tìm thấy giá trị trùng thì mọi giá trị đều khác nhau. Với [3, 1, 4, 1, 5], tập hợp chứa {3, 1, 4} khi số 1 thứ hai xuất hiện.

Tra cứu và thêm phần tử mất trung bình O(1) thời gian, nên lượt duyệt mất O(n). Nếu không có giá trị lặp lại, cuối cùng tập hợp sẽ chứa cả n giá trị.

Thuật toán

Tạo một tập hợp băm rỗng seen.
Với mỗi giá trị trong nums, nếu giá trị đó có trong seen, trả về true.
Nếu không, thêm giá trị đó vào seen.
Sau vòng lặp, trả về false.

def containsDuplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

Lỗi thường gặp và trường hợp biên

Bắt đầu vòng lặp bên trong để kiểm tra từng cặp tại j = i. Khi đó, mọi giá trị đều khớp với chính nó và kết quả luôn là true.
So sánh các phần tử liền kề mà chưa sắp xếp trước. Trong [9, 1, 2, 3, 9], hai số 9 không nằm cạnh nhau.
Bắt đầu vòng lặp kiểm tra các phần tử liền kề tại chỉ số 0 rồi đọc nums[-1]. Hãy bắt đầu từ 1; mảng có một giá trị sẽ trả về chính xác false.
Coi các giá trị có cùng giá trị tuyệt đối là bằng nhau, chẳng hạn bằng cách băm abs(x). -4 và 4 là hai số khác nhau.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán chứa phần tử trùng lặp là gì?

Giải pháp dùng tập hợp băm có độ phức tạp thời gian trung bình là O(n) và dùng thêm O(n) bộ nhớ. Sắp xếp trước mất O(n log n) thời gian và không cần mảng bổ sung nếu bạn có thể sắp xếp lại đầu vào. So sánh từng cặp mất O(n²) thời gian.

Bạn có thể giải bài toán Contains Duplicate mà không cần dùng thêm bộ nhớ không?

Có, nếu bạn có thể sắp xếp lại mảng: hãy sắp xếp mảng tại chỗ rồi so sánh từng giá trị với giá trị liền kề, đổi cách dùng tập hợp có độ phức tạp O(n) lấy thời gian O(n log n). Nếu không sắp xếp lại và không dùng thêm bộ nhớ, lựa chọn duy nhất còn lại là kiểm tra từng cặp với độ phức tạp O(n²).

So sánh kích thước của tập hợp với độ dài của mảng có phải là một lời giải hợp lệ không?

Có. Tạo một tập hợp từ toàn bộ nums rồi kiểm tra xem nó có nhỏ hơn mảng hay không. Cách này chạy trong thời gian O(n) và dùng O(n) bộ nhớ.

def containsDuplicate(nums):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [3, 1, 4, 1, 5]

Đầu ra mong đợi

true