O(1)空间复杂度和O(n)时间复杂度下的循环置换

Question

O(1)空间复杂度和O(n)时间复杂度下的循环置换

arraysalgorithmlanguage-agnosticpermutation

3

我看到了一道面试题，要求交换数组arr[i]和i的值，其中i的范围是[0,n-1]。

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

解释：输入中a[1]=2，因此答案中a[2]=1，以此类推

我尝试了一下，但没有得到正确的答案。

我的思路是：对于每一对数字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);

如果您能提供带有部分解释的伪代码，那么我更容易理解您的答案。

编辑：我了解了这是循环置换，因此更改了问题标题。

- Aseem Goyal

问题不够雄心勃勃：如果你能在O(1)的空间复杂度下解决它，那么你也可以在O(1)的时间复杂度下解决它！ - Gareth Rees

3个回答

1

这是我的建议，O(n) 时间复杂度，O(1) 空间复杂度：

void OrderArray(int[] A)
{
    int X = A.Max() + 1;

    for (int i = 0; i < A.Length; i++)
        A[i] *= X;

    for (int i = 0; i < A.Length; i++)
        A[A[i] / X] += i;

    for (int i = 0; i < A.Length; i++)
        A[i] = A[i] % X;
}

简短说明：

我们使用X作为原始数组中值的基本单位（我们将原始数组中的每个值乘以X，它比A中的任何数字都大-基本上是A的长度+1）。因此，在任何时候，只要我们没有向该单元格添加超过X，就可以通过执行A[i] / X来检索原始数组中某个单元格中的数字。

这使我们拥有两层值，其中A[i]％X表示排序后单元格的值。这两个层不会在整个过程中交叉。

完成后，我们通过执行A[i] = A[i]％X来清除原始值乘以X的A。

希望这已经足够清楚了。

- Ron Teller

你的代码在我尝试的所有测试用例中都像魔法一样正常工作。 - Abhishek Bansal

请您能否解释一下？ - Filipe Gonçalves

0

也许可以通过使用输入排列的图像作为索引来实现：

 void inverse( unsigned int* input, unsigned int* output, unsigned int n )
 {
     for ( unsigned int i = 0; i < n; i++ )
         output[ input[ i ] ] = i;
 }

- anonymous

您使用了额外的空格，这是不允许的。 - Aseem Goyal

请澄清一下：输入置换是否允许包含多个循环？标题中说“循环置换”，但 Abhishek Bansal 代码的反例包含两个循环。 - anonymous

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

以下是我写的Java代码。

对于数组中的每个值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));