Cho một tập hợp số bị bỏ qua, tôi cần tìm số thứ N không tồn tại trong tập hợp đó. Ví dụ:

Cho một tập hợp [1, 4, 5] một số kết quả:

Với N = 1 thì kết quả là 0

Với N = 2 kết quả là 2 (vì 1 bị bỏ qua)

Với N = 3 kết quả là 3 (vì 1 bị bỏ qua)

Với N = 4 kết quả là 6 (vì 1,4,5 bị bỏ qua)

Điều này sẽ hoạt động với N khá lớn, vì vậy giải pháp đơn giản không thể cắt giảm được =(

câu trả lời hay nhất

Một cách là xây dựng một mảng phụ trợ cho bạn biết, đối với mỗi chỉ mục trong mảng, số lượng giá trị còn thiếu bên dưới nó. Ví dụ: trong mảng này:

1 4 5 9 13 (Mảng A)

Mảng này là

1 4 5 9 13 (Mảng A)
1 3 3 6 9 (Mảng B)

Bạn có thể điền mảng B vào thời gian O(n) bằng cách sử dụng:

• B[0] = A[0] (Bạn có hiểu tại sao không?)
• B[n + 1] = B[n] + A[n + 1] - A[n] - 1. Điều này có vẻ bí ẩn nhưng thực ra nó rất đơn giản. Tổng số giá trị còn thiếu trước vị trí n+1 được tính bằng số giá trị còn thiếu trước vị trí n (tức là B[n]) cộng với số phần tử bị thiếu giữa các vị trí A[n+1] và MỘT]. Giá trị là A[n + 1] - A[n] - 1.

Bây giờ bạn có thể quan sát một kết quả quan trọng: với bất kỳ vị trí i nào, giá trị của A[i] được cho bởi B[i] + i. (Kiểm tra nó ở trên). Tại sao lại thế này? Vâng, với bất kỳ vị trí i nào, số số còn thiếu bên dưới nó là B[i]. Phía trước có i số, biểu thị tổng số giá trị nhỏ hơn nó là B[i] + i.

Bây giờ bạn đã có cái này, bạn có thể trả lời các truy vấn có dạng "Số thứ k còn thiếu là gì?" Kịp thời O(log n) bằng thuật toán sau:

• Thực hiện tìm kiếm nhị phân trong mảng B (lưu ý rằng nó đã được sắp xếp!) để tìm giá trị đầu tiên lớn hơn k.
• Nếu mục xuất hiện ở vị trí 0, câu trả lời là k. Lý do cho điều này là bạn đang tìm số thiếu nhỏ thứ k trong mảng và k nhỏ hơn mục đầu tiên trong mảng. Do đó, số bạn muốn chính là k.
• Nếu mục xuất hiện ở một nơi khác (ví dụ ở vị trí x), thì bạn biết rằng x ≠ 0, do đó có một số vị trí trước nó, cụ thể là vị trí x - 1. Vì B[x - 1] ≤ k, bạn biết rằng giá trị bạn muốn phải nằm trong khoảng A[x - 1] và A[x]. Sau đó, nếu bạn trừ B[x] khỏi k, bạn sẽ nhận được chỉ số của số còn thiếu giữa A[x - 1] và A[x]. Do đó, số còn thiếu của bạn là A[x - 1] + k - B[x - 1] + 1.

Ví dụ: hãy lấy mảng trước làm ví dụ:

1 4 5 9 13 (Mảng A)
1 3 3 6 9 (Mảng B)

Giả sử chúng ta muốn giá trị còn thiếu nhỏ thứ 5. Thực hiện tìm kiếm nhị phân của chúng tôi đã tìm thấy vị trí này:

1 4 5 9 13 (Mảng A)
1 3 3 6 9 (Mảng B)
      ^

Sao lưu một chút sẽ đưa chúng ta đến đây:

1 4 5 9 13 (Mảng A)
1 3 3 6 9 (Mảng B)
    ^

Câu trả lời phải là A[i] + k - B[i] + 1. Đây là 5 - 3 + 5 + 1 = 8. đúng rồi:

• Phần tử còn thiếu thứ 0 là 0
• Phần tử còn thiếu đầu tiên là 2
• Phần tử còn thiếu thứ hai là 3
• Phần tử còn thiếu thứ ba là 6
• Phần tử còn thiếu thứ 4 là 7
• Phần tử còn thiếu thứ năm là 8.

Hãy làm thêm một điều nữa: giả sử chúng ta muốn cái thứ 6. Tìm kiếm nhị phân đưa chúng ta đến đây:

1 4 5 9 13 (Mảng A)
1 3 3 6 9 (Mảng B)
        ^

Sao lưu một điểm:

1 4 5 9 13 (Mảng A)
1 3 3 6 9 (Mảng B)
      ^

Chúng tôi muốn A[i] + k - B[i] + 1 = 9 + 6 - 6 + 1 = 10. Đây thực sự là câu trả lời đúng.

Nhìn chung, đây là quá trình tiền xử lý O(n) và mỗi truy vấn có thể được giải quyết trong thời gian O(log n).

希望这对您有所帮助!

Về thuật toán - tìm số thứ n không tồn tại trong tập hợp, chúng tôi tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/22798172/