hoán vị của một vector

Question

giả sử tôi có một vector:

0 1 2 3 4 5 
[45,89,22,31,23,76] 

Và một hoán vị của các chỉ số của nó:

[5,3,2,1,0,4] 

Có một cách hiệu quả để nghỉ mát nó theo hoán vị do đó việc thu thập:

[76,31,22,89,45,23] 

Sử dụng tối đa O (1) không gian bổ sung?

Answer 1

Có. Bắt đầu từ vị trí ngoài cùng bên trái, chúng tôi đặt phần tử vào đúng vị trí i bằng cách hoán đổi nó với phần tử không đúng chỗ khác tại vị trí đó i. Đây là nơi chúng ta cần thêm không gian (1). Chúng tôi tiếp tục trao đổi các phần tử xung quanh cho đến khi phần tử ở vị trí này là chính xác. Chỉ sau đó chúng ta tiến tới vị trí tiếp theo và làm điều tương tự.

Ví dụ:

[5 3 2 1 0 4] trạng thái ban đầu

[4 3 2 1 0 5] hoán đổi (5,4), 5 hiện đang ở đúng vị trí, nhưng 4 vẫn chạy sai

[0 3 2 1 4 5] hoán đổi (4,0), bây giờ cả 4 và 0 là ở các vị trí chính xác, chuyển sang vị trí tiếp theo

[0 1 2 3 4 5 ] hoán đổi (3,1), bây giờ 1 và 3 đều ở đúng vị trí, chuyển sang vị trí kế tiếp

[0 1 2 3 4 5] tất cả các yếu tố đều ở đúng vị trí, kết thúc.

Note:

Vì mỗi nghiệp vụ hoán đổi đặt ít nhất một (hai) các yếu tố vào đúng vị trí, chúng ta cần không quá N giao dịch hoán đổi như vậy hoàn toàn.

Answer 2

Giải pháp của Zach rất tốt.

Tuy nhiên, tôi đã tự hỏi tại sao cần phải sắp xếp. Nếu bạn có hoán vị của các chỉ mục, hãy sử dụng các giá trị như một con trỏ tới mảng cũ.

Điều này có thể loại bỏ nhu cầu sắp xếp mảng ở vị trí đầu tiên. Đây không phải là một giải pháp có thể được sử dụng trong mọi trường hợp, nhưng nó sẽ hoạt động tốt trong hầu hết các trường hợp.

Ví dụ:

a = [45,89,22,31,23,76]; 
b = [5,3,2,1,0,4] 

Bây giờ nếu bạn muốn lop qua các giá trị trong một, bạn có thể làm điều gì đó tương tự (pseudo-code):

for i=0 to 4 
{ 
    process(a[i]); 
} 

Nếu bạn muốn lặp qua các giá trị theo thứ tự mới, làm:

for i=0 to 4 
{ 
    process(a[b[i]]); 
} 

Như đã đề cập đến tai lier, soluion này có thể là đủ trong nhiều trường hợp, nhưng có thể không trong một số trường hợp khác. Đối với các trường hợp khác, bạn có thể sử dụng giải pháp của Zach.Nhưng đối với những trường hợp mà giải pháp này có thể được sử dụng, nó là tốt hơn bởi vì không có phân loại là cần thiết cả.