3

我看到一个面试问题，要求
Interchange arr[i] and i for i=[0,n-1]

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

解释：a[1]=2 in input , so a[2]=1 in answer so on

我尝试了这个但没有得到正确的答案。

我能做的是：for a pair of numbers p and q , a[p]=q and 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);

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

编辑：我来到 knpw 它是循环排列所以改变了问题标题。

4

3 回答 3

3

以下是我想出的（Java代码）。

对于 中的每个值x，a它设置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));
于 2013-10-24T09:59:05.583 回答
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，它大于任何数字- 基本上是+ 1A的长度）。A所以在任何时候我们都可以通过做数组来检索原始数组的某个单元格中的数字，A[i] / X只要我们没有添加超过X那个单元格。

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

完成后，我们清除A乘以 perform 的原始X值A[i] = A[i] % X。

希望足够干净。

于 2013-10-24T10:10:39.317 回答
0

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

 void inverse( unsigned int* input, unsigned int* output, unsigned int n )
 {
     for ( unsigned int i = 0; i < n; i++ )
         output[ input[ i ] ] = i;
 }
于 2013-10-24T09:01:18.987 回答