Missing Number

Q: Độ phức tạp thời gian của bài toán Missing Number là gì?

Cả lời giải dùng tổng và XOR đều chạy trong thời gian O(n) với bộ nhớ bổ sung O(1) : chúng đọc mỗi giá trị một lần và chỉ lưu một số. Tìm kiếm trong danh sách cho từng ứng viên mất O(n²) , còn sắp xếp trước rồi tìm khoảng trống mất O(n log n) .

DễThao tác bit Toán và mô phỏng

+10

Bạn nhận được một danh sách nums gồm n số nguyên khác nhau, mỗi số nằm trong khoảng từ 0 đến n. Khoảng từ 0 đến n có n+1 số, vì vậy có đúng một số không có trong danh sách. Hãy trả về số còn thiếu đó.

Hàm

missingNumber(nums: integer-array) → integer

numsinteger-array: n số nguyên phân biệt trong khoảng từ 0 đến n, theo thứ tự bất kỳ
Trả vềinteger: một số duy nhất từ 0 đến n không có trong nums

Ràng buộc

n == nums.length
1 ≤ n ≤ 10⁴
0 ≤ nums[i] ≤ n
Tất cả giá trị trong nums đều khác nhau.

Ví dụ

Đầu vào: nums = [4, 2, 0, 1]
Đầu ra: 3
Giải thích: Danh sách có 4 giá trị, nên phạm vi là từ 0 đến 4. Danh sách chứa 0, 1, 2 và 4, còn 3 là số duy nhất không khớp.

Câu hỏi mở rộng

Nếu danh sách đã được sắp xếp, bạn có thể tìm số còn thiếu trong thời gian O(log n) bằng tìm kiếm nhị phân 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

Bạn biết danh sách cần chứa gì: mọi số nguyên từ 0 đến n. Rút gọn toàn bộ khoảng số và danh sách thành một giá trị tổng hợp cho mỗi bên, tổng hoặc XOR, rồi lấy hiệu giữa hai giá trị để tìm số bị thiếu. Cách này chỉ cần duyệt một lần và không cần thêm bộ nhớ.

Kiểm tra mọi ứng viên

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Lần lượt xét các ứng viên từ 0 đến n, với mỗi ứng viên, hãy quét danh sách. Mỗi số trong khoảng này hoặc có trong danh sách, hoặc là đáp án, nên ứng viên đầu tiên không khớp với số nào chính là số còn thiếu.

Mỗi ứng viên cần quét tối đa n giá trị. Với n = 10^4 và khoảng trống gần cuối, số phép so sánh vào khoảng 5 × 10^7.

Thuật toán

Lặp candidate từ 0 đến n, bao gồm cả n.
Duyệt nums để tìm giá trị bằng candidate.
Nếu tìm thấy giá trị đó, chuyển sang candidate tiếp theo.
Nếu duyệt xong mà không tìm thấy giá trị khớp, trả về candidate.

def missingNumber(nums):
    n = len(nums)
    for candidate in range(n + 1):
        # "in" on a list scans it from the start: O(n) per candidate.
        if candidate not in nums:
            return candidate
    return -1

Trừ tổng khỏi tổng dự kiến

Ý tưởng

Tổng các số từ 0 đến n là n(n+1)/2. Danh sách là tập hợp đầy đủ đó nhưng thiếu một số, nên tổng của danh sách thấp hơn đúng bằng số bị thiếu. Với [4, 2, 0, 1], tổng các số trong phạm vi là 4 × 5 / 2 = 10, còn tổng danh sách là 7, vậy số bị thiếu là 3.

Chỉ cần duyệt qua danh sách một lần để tính tổng: thời gian O(n) và một tổng lũy kế.

Thuật toán

Gọi n là độ dài của nums.
Tính tổng đầy đủ n(n+1)/2.
Cộng tất cả giá trị trong nums.
Trả về tổng đầy đủ trừ đi tổng của danh sách.

def missingNumber(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)

Thực hiện phép XOR giữa các chỉ số và giá trị

Ý tưởng

XOR triệt tiêu các cặp: a ^ a là 0, a ^ 0 là a, và thứ tự không quan trọng. XOR các chỉ số từ 0 đến n cùng với các giá trị. Một số trong danh sách xuất hiện một lần dưới dạng chỉ số và một lần dưới dạng giá trị, nên chúng triệt tiêu lẫn nhau. Số bị thiếu chỉ xuất hiện dưới dạng chỉ số, nên đó là số còn lại. Vòng lặp duyệt các chỉ số từ 0 đến n-1, vì vậy hãy bắt đầu kết quả với n.

Với [4, 2, 0, 1]: bắt đầu với 4, sau đó XOR thêm 0 và 4, 1 và 2, 2 và 0, 3 và 1. Mọi số trừ 3 đều xuất hiện hai lần, nên còn lại 3. Giá trị tích lũy không bao giờ dùng nhiều bit hơn n, vì vậy nó không thể bị tràn.

Thuật toán

Đặt result bằng n, độ dài của nums.
Với mỗi chỉ số i, thực hiện XOR result với i và với nums[i].
Trả về result.

def missingNumber(nums):
    # Start with n, the one index the loop below never reaches.
    result = len(nums)
    for i, value in enumerate(nums):
        result ^= i ^ value
    return result

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

Quên rằng bản thân n cũng có thể bị thiếu. Với [0, 1, 2], đáp án là 3, không phải một chỉ số; phiên bản XOR phải bắt đầu từ n.
Dùng sai kích thước khoảng. Từ 0 đến n có n+1 số, vì vậy tổng đầy đủ là n(n+1)/2, không phải (n-1)n/2.
Bắt đầu tìm kiếm từ 1. Với [1], đáp án là 0.
Tràn số trong phiên bản tính tổng với đầu vào lớn hơn. Với phép tính 32 bit, n(n+1) bị tràn khi n vượt quá khoảng 46.000. Hãy dùng phép tính 64 bit hoặc XOR.

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

Độ phức tạp thời gian của bài toán Missing Number là gì?

Cả lời giải dùng tổng và XOR đều chạy trong thời gian O(n) với bộ nhớ bổ sung O(1): chúng đọc mỗi giá trị một lần và chỉ lưu một số. Tìm kiếm trong danh sách cho từng ứng viên mất O(n²), còn sắp xếp trước rồi tìm khoảng trống mất O(n log n).

Bạn nên dùng công thức tính tổng hay XOR?

Cả hai đều chỉ cần duyệt một lần và dùng bộ nhớ cố định. Cách tính tổng dễ giải thích hơn, nhưng tích trung gian cần dùng số nguyên 64 bit khi n vượt khoảng 46.000. XOR không bao giờ bị tràn.

Bạn có thể giải bài toán Missing Number bằng tập hợp băm không?

Có. Đưa mọi giá trị (value) vào một tập hợp (set), rồi kiểm tra từ 0 đến n và trả về số đầu tiên không có trong tập hợp. Cách này chạy trong thời gian O(n) nhưng dùng thêm O(n) bộ nhớ, điều mà các phương pháp tổng và XOR tránh được.

def missingNumber(nums):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [4, 2, 0, 1]

Đầu ra mong đợi

Missing Number

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Kiểm tra mọi ứng viên

Trừ tổng khỏi tổng dự kiến

Thực hiện phép XOR giữa các chỉ số và giá trị

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

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

Bài tập tương tự