给定一个数组arr和一个索引数组ind，我想arr 就地重新排列以满足给定的索引。例如：
var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];
rearrange(arr, ind);
console.log(arr); // => ["B", "E", "D", "F", "A", "C"]
这是一个可能使用O(n)时间和O(1)空间，但会发生ind变化的解决方案：
function swap(arr, i, k) {
var temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
function rearrange(arr, ind) {
for (var i = 0, len = arr.length; i < len; i++) {
if (ind[i] !== i) {
swap(arr, i, ind[i]);
swap(ind, i, ind[i]);
}
}
}
如果我们限于空间并且不允许变异，那将是最佳解决方案？O(1)ind
编辑：上面的算法是错误的。看到这个问题。
这是“符号位”解决方案。
鉴于这是一个JavaScript问题，因此ind数组中指定的数字文字存储为带符号的浮点数，因此在输入所使用的空间中有一个符号位可用。
该算法根据ind数组循环遍历元素，并将元素移位到位，直到它返回到该循环的第一个元素。然后找到下一个循环并重复相同的机制。
该IND阵列执行期间修改，但将在该算法的完成时恢复到原来的。您在其中一项评论中提到这是可以接受的。
该IND阵列由签署花车，即使他们都是非负（整数）。符号位用作指示该值是否已被处理的指示符。通常，这可以被认为是额外的存储（n位，即O（n）），但是由于存储已经被输入占用，因此它不是额外的已获取空间。代表循环最左边成员的ind值的符号位未更改。
编辑：我取代了使用的~操作者，因为它不会产生所期望的结果对数等于或大于2 31，而的JavaScript应该支持的数字被用作数组索引高达至少2 32 - 1。所以现在我改为使用k = -k-1，这是相同的，但是适用于整个浮点数范围，可以安全地用作整数。请注意，作为另一种选择，可以使用浮点数的小数部分（+/- 0.5）。
这是代码：
var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];
rearrange(arr, ind);
console.log('arr: ' + arr);
console.log('ind: ' + ind);
function rearrange(arr, ind) {
var i, j, buf, temp;
for (j = 0; j < ind.length; j++) {
if (ind[j] >= 0) { // Found a cycle to resolve
i = ind[j];
buf = arr[j];
while (i !== j) { // Not yet back at start of cycle
// Swap buffer with element content
temp = buf;
buf = arr[i];
arr[i] = temp;
// Invert bits, making it negative, to mark as visited
ind[i] = -ind[i]-1;
// Visit next element in cycle
i = -ind[i]-1;
}
// dump buffer into final (=first) element of cycle
arr[j] = buf;
} else {
ind[j] = -ind[j]-1; // restore
}
}
}尽管该算法具有嵌套循环，但仍可以在O（n）时间内运行：交换每个元素仅发生一次，并且外循环仅访问每个元素一次。
变量声明表明内存使用情况是恒定的，但要注意的是，也要使用ind数组元素的符号位（在输入已分配的空间中）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句