Tìm số nguyên 32 bit bị thiếu trong một mảng chưa phân loại chứa tối đa 4 tỷ ints

Question

Đây là số problem được mô tả trong Programming pearls. Tôi không thể hiểu được phương pháp tìm kiếm nhị phân mà tác giả đã bỏ qua. Bất kỳ ai có thể giúp xây dựng? Cảm ơn.

EDIT: Tôi có thể hiểu tìm kiếm nhị phân nói chung. Tôi chỉ không thể hiểu làm thế nào để áp dụng tìm kiếm nhị phân trong trường hợp đặc biệt này. Làm thế nào để quyết định số bị thiếu là trong hoặc không trong một số phạm vi để chúng tôi có thể chọn một số khác. Tiếng Anh không phải là ngôn ngữ mẹ đẻ của tôi, đó là một lý do tôi không thể hiểu rõ tác giả. Vì vậy, hãy sử dụng ngôn ngữ đơn giản bằng tiếng Anh :)

EDIT: Cảm ơn tất cả các bạn đã có câu trả lời và nhận xét tuyệt vời! Bài học quan trọng nhất tôi không giải được câu hỏi này là Tìm kiếm nhị phân không chỉ áp dụng cho mảng được sắp xếp!

Answer 1

có một số chi tiết thông tin về this web site Trích dẫn từ đó:..

"đó là hữu ích để xem nhị phân này tìm kiếm theo hai mươi bit đại diện cho mỗi số nguyên. chúng tôi đọc (tối đa) một triệu số nguyên đầu vào và viết các số nguyên đó bằng bit không đầu vào một băng và những phần có bit đầu tiên đến một băng khác. Một trong hai băng có chứa tối đa 500.000 số nguyên, vì vậy chúng tôi sử dụng băng đó làm đầu vào hiện tại và lặp lại quá trình thăm dò, nhưng lần này vào bit thứ hai. Nếu băng đầu vào ban đầu chứa N phần tử, thì giá trị đầu tiên sẽ đọc N số nguyên, lần thứ hai vượt qua tối đa N/2, lần vượt qua thứ ba ở hầu hết N/4, và cứ như vậy, tổng thời gian chạy là tỷ lệ thuận với N. số nguyên còn thiếu có thể được tìm thấy bằng cách phân loại trên băng và sau đó quét, nhưng điều đó sẽ yêu cầu thời gian tỷ lệ với N log N. "

Như bạn thấy, đây là một biến thể trên thuật toán tìm kiếm nhị phân: chia thành hai phần và giải quyết vấn đề cho một trong những phần nhỏ hơn.

Answer 2

Vâng, đó là về một tệp có chứa tất cả 4 tỷ số nguyên trừ một! Đó là bắt trong trường hợp này.

1. Khi bạn di chuyển dọc theo danh sách các số nguyên, hãy tính tổng.
2. Cuối cùng, tính tổng như thể có tất cả các số nguyên hiện tại bằng công thức N * (N + 1)/2
3. Trích tổng tại (1) từ số tiền bạn tính tại (2). Đó là số nguyên còn thiếu.

Ví dụ: Giả sử chúng tôi có trình tự sau: 9 3 2 8 4 10 6 1 7 (1 đến 10 với 5 mất tích). Khi chúng ta thêm số nguyên tuần tự, chúng ta nhận được 9 + 3 + 2 + 8 + 4 + 10 + 6 + 1 + 7 = 50. Tổng của tất cả các số nguyên từ 1 đến 10 sẽ là 10 * (10 + 1)/2 = 55 Do đó, số nguyên còn thiếu là 55 - 50 = 5. QED

Answer 3

Tôi tin rằng tác giả đang nhận được là bạn chọn điểm giữa của phạm vi số hiện tại của mình và chuẩn bị hai tệp đầu ra. Khi bạn đọc đầu vào của mình, mọi thứ phía trên điểm giữa sẽ đi vào một tệp và mọi thứ bên dưới điểm giữa sẽ đi vào điểm khác. Sau khi kết thúc, bạn chọn bất kỳ tệp nào nhỏ hơn, và sau đó lặp lại thao tác, sử dụng [giới hạn dưới, điểm giữa] hoặc (điểm giữa, giới hạn trên) làm phạm vi mới cho đến khi tệp và phạm vi đủ nhỏ để chuyển sang mô hình bitmap (hoặc một trong các tập tin đầu ra của bạn là trống)

Damien

Answer 4

Ý tưởng chung là: chọn một dải số nguyên và chọn tất cả các số nguyên nằm trong phạm vi đó. Nếu số lượng số nguyên nhỏ hơn kích thước của phạm vi của bạn, bạn biết rằng phạm vi đó chứa một hoặc nhiều số bị thiếu.

Điều này áp dụng cho vấn đề ban đầu về cách bạn biết có một số số bị thiếu ở địa điểm đầu tiên.

Answer 5

Nếu bạn xem xét các số trong phạm vi từ 1 đến N; một nửa trong số chúng lớn hơn N/2 và một nửa trong số chúng nhỏ hơn N/2

Những cái lớn hơn N/2 sẽ có MSB được đặt thành một; MSB = 0 cho những cái nhỏ hơn.

phân vùng toàn bộ thiết lập dựa trên MSB mà sẽ cung cấp cho bạn hai bộ: tập hợp các số nhỏ hơn N/2 và tập hợp các số lớn hơn N/2

Các phân vùng kích thước nhỏ hơn có yếu tố thiếu .

Trong bước tiếp theo, hãy sử dụng MSB tiếp theo.

1. Nếu các thiết lập nhỏ hơn là ít hơn N/2, một nửa trong số đó là ít hơn N/4 (2 MSB = 0) và nửa còn lại lớn hơn N/4 (2 MSB = 1)

2. Nếu tập nhỏ hơn lớn hơn N/2, một nửa trong số đó nhỏ hơn N/2 + N/4 (2 MSB = 0) và nửa kia lớn hơn N/2 + N/4 (MSB thứ 2 = 1)

Mỗi vòng sẽ giảm một nửa không gian tìm kiếm.

Sum (N/2^i) for 0 <= i < log N gives you O(N) 

Answer 6

Đây là câu hỏi cơ bản giống như this question. Cách tiếp cận tương tự cũng hoạt động ở đây đối với trường hợp bộ nhớ phong phú để có được độ phức tạp O (N). Về cơ bản chỉ đệ quy cố gắng đặt mọi số nguyên vào vị trí chính xác của nó và xem những gì không có giá trị chính xác.