根据给定索引对数组重新排序

本文介绍了根据给定索引对数组重新排序的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

算法根据给定索引对数组重新排序

Algorithm reorder array according to given index

a[] = [50, 40, 70, 60, 90] index[] = [3, 0, 4, 1, 2] a= [60,50,90,40,70]

在 O(n) 中并且没有额外的数组/空格

in O(n) and With out extra array/spaces

推荐答案

您将需要用于临时变量和循环计数器/索引的空间.根据算法通常的重新排序"也会将 index[] 改回 {0, 1, 2, 3, 4}.

You'll need space for a temp variable and loop counters / indices. The usual "reorder" according to algorithm is also going to change index[] back to {0, 1, 2, 3, 4}.

提示，注意 index[] 中索引的顺序.

Hint, noting the ordering of indices in index[].

{0, 1, 2, 3, 4} index[] = {3, 0, 4, 1, 2}

可以按照循环"进行重新排序.从 index[0] 开始，如果你查看 index[0]，然后查看 index[index[0]]，请注意循环"，依此类推...

The reordering can be done by following the "cycles". Start with index[0], and note the "cycles" if you look at index[0], then index[index[0]], and so on ...

// 1st cycle index[0] == 3 // cycle starts at 0 index[3] == 1 index[1] == 0 // end of cycle since back at 0 // 2nd cycle index[2] == 4 // cycle starts at 2 index[4] == 2 // end of cycle since back at 2

示例 C 代码:

#include <stdio.h> static int A[] = {50, 40, 70, 60, 90}; static int I[] = {3, 0, 4, 1, 2}; int main() { int i, j, k; int tA; /* reorder A according to I */ /* every move puts an element into place */ /* time complexity is O(n) */ for(i = 0; i < sizeof(A)/sizeof(A[0]); i++){ if(i != I[i]){ tA = A[i]; j = i; while(i != (k = I[j])){ A[j] = A[k]; I[j] = j; j = k; } A[j] = tA; I[j] = j; } } for(i = 0; i < sizeof(A)/sizeof(A[0]); i++) printf("%d ", A[i]); return 0; }

相同的算法，但使用交换而不是移动(这是较慢的方法).

The same algorithm, but using swaps instead of moves (this is slower method).

#include <stdio.h> #define swap(a, b) {(a)^=(b); (b)^=(a); (a)^=(b);} static int A[] = {50, 40, 70, 60, 90}; static int I[] = {3, 0, 4, 1, 2}; int main() { int i, j, k; /* reorder A according to I */ /* every swap puts an element into place */ /* last swap of a cycle puts both elements into place */ /* time complexity is O(n) */ for(i = 0; i < sizeof(A)/sizeof(A[0]); i++){ if(i != I[i]){ j = i; while(i != (k = I[j])){ swap(A[j], A[k]); I[j] = j; j = k; } I[j] = j; } } for(i = 0; i < sizeof(A)/sizeof(A[0]); i++) printf("%d ", A[i]); return 0; }