Tìm ánh xạ duy nhất giữa các phần tử của hai mảng có cùng kích thước

Question

Gần đây tôi đã được hỏi câu hỏi này trong một cuộc phỏng vấn:

Có hai mảng có kích thước 'n'. Một mảng có đai ốc, cái kia có bu lông. Mỗi hạt phù hợp chính xác một bu lông và ngược lại. Khi bạn so sánh đai ốc bằng bu lông, bạn nhận được một trong 3 kết quả: chặt chẽ, lỏng lẻo, vừa vặn.

Làm thế nào để bạn tìm thấy bản đồ độc đáo một cách hiệu quả?

Không thể sắp xếp trên một trong các bộ. Bạn không bao giờ biết nếu b1 nhỏ hơn b2 hoặc
n1 nhỏ hơn n2. Trong đó n1, n2 là các hạt và b1, b2 là các bu lông. Chỉ có điều bạn có thể làm là so sánh một hạt với một bu lông và nhận được kết quả: chặt chẽ, vừa vặn, lỏng lẻo.

Answer 1

Các quicksort như thuật toán thực hiện công việc:

1. ngẫu nhiên chọn một hạt n và sử dụng nó như trục để phân vùng các bộ bu lông B thành ba bộ: chặt chẽ (B1), lỏng (B2), phù hợp .
2. Đánh dấu chốt phù hợp là b. Bây giờ bạn sử dụng bu-lông này làm trục xoay để phân chia các bộ hạt N\n thành hai bộ: chặt (N1) hoặc lỏng lẻo (N2).
3. Bây giờ bạn có ba cặp: N1 và B1, n và b, N2 và B2. Tất cả chúng đều có cùng kích thước. Bạn có thể làm cùng một phân vùng đệ quy trên (N1,B2) và (N2,B1) và bạn có thể nhận được câu trả lời cuối cùng.

Rõ ràng sự phức tạp là O(N log N), giống như quicksort.

Answer 2

Lấy một hạt N0 và so sánh nó với tất cả các bu lông. Với thông tin kết quả, chúng ta có thể chia mảng bu lông thành [bolts smaller than B0] + B0 + [bolts larger than B0]. Luôn có một số B0 duy nhất phù hợp với N0 dựa trên tuyên bố của câu hỏi.

Sau đó lấy hạt tiếp theo N1 và so sánh nó với B0. Nếu kết quả là "chặt chẽ", chúng tôi tìm kiếm một nửa nhỏ hơn như chúng tôi đã làm ở trên với N0. Nếu không, chúng tôi làm tương tự nhưng với một nửa lớn hơn. Làm điều này sẽ tiếp tục chia một nửa hai phần thành 2.

Tiếp tục thực hiện việc này cho đến khi bạn đã làm việc thông qua tất cả các loại hạt. Điều này tương đương với quicksort. Trường hợp trung bình là O (N logN), nhưng có trường hợp phức tạp rõ ràng nhất của O (N^2) khi danh sách được "sắp xếp" rồi.

Answer 3

Đối với phân tích chính thức (bao gồm quicksort) thấy http://www.wisdom.weizmann.ac.il/~naor/PUZZLES/nuts_solution.html và http://compgeom.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/05-nutsbolts.pdf