arrays - O(1) 空间和 O(n) 时间的循环置换

Question

我看到一个面试题，要求

交换 arr[i] 和 i 为 i=[0,n-1]

例子: 输入:1 2 4 5 3 0
答案:5 0 1 4 2 3

解释:a[1]=2 in input ，所以 a[2]=1 in answer so on

我试过了，但没有得到正确答案。

我能做的是:对于一对数字 p 和 q，a[p]=q 和 a[q]=p。

欢迎提出任何改进建议。

FOR(j,0,n-1)
{
    i=j;
    do{
        temp=a[i];
        next=a[temp];
        a[temp]=i;
        i=next;
    }while(i>j);
}
print_array(a,i,n);  

如果它包含带有一些解释的伪代码，我会更容易理解您的答案。

编辑:我知道它是循环排列所以改变了问题标题。

Answer 1

下面是我想出的(Java 代码)。

对于 a 中的每个值 x，它将 a[x] 设置为 x，并设置 x 到覆盖值(用于 a[a[x]])，并重复直到它回到原始 x。

我使用负值作为标志来指示该值已被处理。

运行时间:

由于它只处理每个值一次，因此运行时间为 O(n)。

代码:

int[] a = {1,2,4,5,3,0};
for (int i = 0; i < a.length; i++)
{
   if (a[i] < 0)
      continue;
   int j = a[i];
   int last = i;
   do
   {
      int temp = a[j];
      a[j] = -last-1;
      last = j;
      j = temp;
   }
   while (i != j);
   a[j] = -last-1;
}
for (int i = 0; i < a.length; i++)
   a[i] = -a[i]-1;
System.out.println(Arrays.toString(a));