2014-05-01 01:23
原题：
WAP to modify the array such that arr[I] = arr[arr[I]].
Do this in place i.e. with out using additional memory. example : if a = {,,,}
o/p = a = {,,,} Note : The array contains to n- integers.
题目：给定一个长度为n的数组，由0至n - 1的排列组成。请做这样的变换，arr[i] = arr[arr[i]]。要求就地完成，不用额外数组。
解法：当数据范围有明确限制时，能够通过压缩维度来节省空间。对于一个数对(x, y)，如果x和y都属于[0, n - 1]，那么x * n + y就能唯一表示这个数对了。因此，可以先把变换后的结果存在高位上，然后再把高位的数通过除法移动到低位。算法是线性的，能够就地完成。
代码：
// http://www.careercup.com/question?id=4909367207919616
#include <cstdio>
#include <vector>
using namespace std; void displaceInPlace(vector<int> &v)
{
int i;
int n; // all elements in the array has value between 0 and n - 1.
n = (int)v.size();
for (i = ; i < n; ++i) {
v[i] = v[v[i]] % n * n + v[i];
}
for (i = ; i < n; ++i) {
v[i] = v[i] / n;
}
} int main()
{
int i, n;
vector<int> v; while (scanf("%d", &n) == && n > ) {
v.resize(n);
for (i = ; i < n; ++i) {
scanf("%d", &v[i]);
}
displaceInPlace(v);
for (i = ; i < n; ++i) {
printf((i ? " %d" : "%d"), v[i]);
}
putchar('\n');
v.clear();
} return ;
}