arrays - 仅使用交换来改变数组顺序

Question

假设您有两个数组，a 和 b。a 的数据对您完全隐藏。您可以对 a 执行的唯一操作是交换两个元素。b 的数据是完全暴露且可变的。

位置 i 处的 b 值指示存储在 a[i] 中的值的目的地。也就是说，如果 b[3] = 7，我们希望将 a[3] 中的值移动到 a[7] 中。我正在尝试编写一个算法，该算法根据数组 b 中的信息仅使用 a 上的交换操作（最好是线性时间和恒定空间）来改变数组 a。举个例子：

if   a  = { a b c d e f }
and  b  = { 1 3 2 0 5 4 }
then a' = { d a c b f e }
(ie, a[i] = a'[b[i]])

我尝试了一种幼稚的方法，即遍历 b 并愉快地执行 a.Swap(i, b[i])，一直在吹口哨，但结果最终会重写自身并移动已经在正确位置的数据（如你可能会猜到）。

编辑：这真的必须是线性时间。它用于并行排序算法，因此速度至关重要。

score 1 · Accepted Answer

Go中的解决方案：

for i := 0; i != len(b); i++ {
    for b[i] != i {
        a.Swap(i, b[i])
        b.Swap(i, b[i])
    }
}

这可能不会立即看起来 O(n)，但请注意

如您所见，该算法在时间上为 O(n)，在空间上为 O(1)。

score 0 · Accepted Answer

按升序排列 b 的元素，在交换 b 的元素时，也交换 a 中的元素。例如，使用冒泡排序：

for(int i=0;i<b.length;i++){
for(int j=0;j<b.length-i-1;j++){
if(b[j+1]<b[j]){
// swap b[j+1] and b[j]
// swap a[j] and a[j+1]
}
}
}

2 回答 2