Hai mảng này có hoán vị nhau không?

Question

thể trùng lặp:
Check if array B is a permutation of A

Với 2 mảng số nguyên được phân loại a và b kích thước bằng nhau. Xác định nếu b là một hoán vị của a. Điều này có thể được thực hiện trong O(n) time và O(1) space không?

Giải pháp đầu tiên xuất hiện trong đầu tôi là sử dụng XOR, tức là XOR all the elements of a and b and if the resultant is 0 which means that b is a permutation of a. Nhưng ông đưa ra những ví dụ mà cách tiếp cận này không thành công. Đối với ví dụ -

a: [1 6 0 0 4] -- b: [1 0 6 1 5] 
a: [1 6 0 0 5] -- b: [1 0 6 1 4] 

Bất kỳ một có bất kỳ ý tưởng, rằng làm thế nào để làm điều đó trong O(n) time và O(1) space?

Answer 1

Nếu các yếu tố thiết lập của bạn là không âm, và bạn có một kiểu số nguyên không giới hạn (một BigInteger hoặc tương tự) có sẵn, bạn có thể định nghĩa một hàm trên một tập A:

C(A) = product(p_(a+1))) cho mỗi a trong A

trong đó p_n là số nguyên tố n. Sau đó, C chỉ phụ thuộc vào các giá trị trong A, thay vì thứ tự của chúng; và bất kỳ thay đổi nào đối với các giá trị thay đổi C.

Ví dụ,

C([1 6 0 0 4]) = p_2.p_7.p_1.p_1.p_5 = 3.17.2.2.11 = 2244 

(và rõ ràng là bất kỳ thiết lập với các yếu tố tương tự có cùng C, bất kể thứ tự), và

C([1 6 0 1 4]) = p_2.p_7.p_1.p_2.p_5 = 3.17.2.3.11 = 3366 

vì vậy chúng tôi biết những bộ khác nhau. Điều này sử dụng định lý cơ bản của số học mà nói rằng bất kỳ số nguyên lớn hơn 1 có thể được viết như một sản phẩm duy nhất (lên đến thứ tự của các yếu tố) của số nguyên tố. Hoặc có thể nó sử dụng một hệ quả. Tôi chỉ làm phương pháp này lên, vì vậy nó có thể không hoạt động. bài này không phải là một nỗ lực tại một bằng chứng về tính đúng đắn của nó ...

Answer 2

Trong trường hợp của một loạt chặn các số nguyên - hãy phạm vi đó được [n,m] mà m-n = U bạn có thể sắp xếp các mảng sử dụng in place radix sort, cũng đã thảo luận trong this great post.

Sau khi bạn có hai mảng được sắp xếp - một phép lặp đơn giản trên cả hai có thể cho bạn câu trả lời - các mảng ban đầu là hoán vị của nhau nếu và chỉ khi các mảng được sắp xếp giống nhau.

Lưu ý:
Có một số "gian lận" trong câu trả lời này [vì vậy tôi đã không gửi nó cho đến khi OP hỏi cho nó trong ý kiến ​​..], vì sự phức tạp thời gian của nó là O(nlogU), và không gian là O(logU). Tuy nhiên, đối với phạm vi bị chặn - chúng tôi có thể giả định O(logU) = O(1) và đối với những trường hợp này, chúng tôi nhận được không gian O(n) và O(1) không gian.

Answer 3

Giải pháp OR độc quyền của bạn về cơ bản là giải pháp dựa trên hàm băm, nhưng sử dụng hàm băm chất lượng kém.

Những gì bạn muốn là một hàm băm mà ...

1. Cho băm mà cực kỳ khó có khả năng va chạm, để họ có thể được coi là định danh duy nhất cho các số nguyên. Git sử dụng băm SHA-1 để xác định các phiên bản mã nguồn, với xác suất va chạm quá thấp, nó có thể bị bỏ qua.

2. Giao hoán (như xor và cộng) và có thể là kết hợp, do đó thứ tự của các mục không thay đổi kết quả băm.

Yêu cầu thứ hai có lẽ là điều khó xử. Tôi đã dành một ít thời gian trong Google, nhưng chỉ sợ những từ như "Quasigroup".