m số nguyên bị thiếu trong một mảng có kích thước n

Question

Đây là một câu hỏi thú vị mà tôi đã gặp phải trong một thời gian trước và đã gặp một số vấn đề khi giải quyết nó.

Có một mảng số nguyên được phân loại kích thước N lưu trữ với số 1,2 .., N + M , với M số nguyên thiếu từ nó. M và N được biết trước mặt. Viết một thuật toán để tìm số thiếu M số nguyên theo cách hiệu quả nhất.

Đã cố gắng lập bản đồ nó vào một mảng có kích thước N + M, do đó i chỉ số thứ chứa các phần tử với giá trị i, nhưng điều này đòi hỏi 2 quét (1 cho lập bản đồ, 1 để tìm số M số bị thiếu).

Cuốn sách mà tôi đề cập đến điều này đề cập đến một giải pháp quét đơn lẻ là có thể nhưng tôi không thể đến được nó. Bất kỳ ý tưởng về cách đi về điều này?

Answer 1

Bạn có thể thực hiện việc này với danh sách được liên kết kép được lập bản đồ trên đầu một mảng.

position 1 2 3 4 5 6 ... 
next  2 3 4 5 6 7 ... 
prev  0 1 2 3 4 5 ... 

Khi vượt qua đầu vào, bạn chỉ mục vào vị trí tương ứng với mỗi số đầu vào và cập nhật danh sách liên kết để xóa (bỏ qua) vị trí đó khỏi danh sách được liên kết. Vào cuối đầu vào, danh sách liên kết sẽ chỉ chứa các vị trí không được truy cập.