c - 置换 i 和 T[i]

Question

假设我有一个 int T 数组，我正在寻找一种置换 i 和 T[i]

的就地算法

我有:[3 2 0 1] (a)

我想要:[2 3 1 0] (b)

例如。在 (b) 中 T[0] = 2 因为在 (a) 中 T[2] 等于 0。

我期待找到一个简单的 O(n) 时间，O(1) 空间算法，但我找不到。有什么想法吗？

注意:

• 有一个单数组，(a)在前，(b)在后。

• 数组中的值属于[0, N[, 无重复。

Answer 1

要得到排列的反转，你只需要遍历排列的循环

int i, j, next, prev;
for(int i=0; i<N; i++) {
  if(T[i]>=N) continue;
  j=T[i];
  prev=i;
  while(j < N) {
    next=T[j];
    T[j]=prev+N;
    prev=j;
    j=next;
  }
}
for(int i=0; i<N; i++)
  T[i]-=N;

我使用大于 N 的数字来标记这是已处理的循环的一部分。