在给定目标索引数组 ind
的情况下,您将如何对给定数组 arr
in-place 进行排序?
例如:
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"]
arr = ["A", "B", "C", "D"];
ind = [ 2, 3, 1, 0 ];
rearrange(arr, ind);
console.log(arr); // => ["D", "C", "A", "B"]
我尝试了以下算法,但在上面的第二个示例中失败了。
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(n) 时间和 O(1) 额外空间内解决这个问题?
您能否证明您的算法有效?
注意:这个问题看起来类似于this one , 但这里允许改变 ind
。
最佳答案
该算法失败,因为它对列表的索引只有一个循环。
在你的算法中发生的是这样的:
i=0 -> ["A", "B", "C", "D"] , [ 2, 3, 1, 0 ]
i=1 -> ["C", "B", "A", "D"] , [ 1, 3, 2, 0 ]
i=2 -> ["C", "D", "A", "B"] , [ 1, 0, 2, 3 ]
i=3 -> ["C", "D", "A", "B"] , [ 1, 0, 2, 3 ]
请注意,在第一次交换时,1
位于 0
位置,除非将其与 0
交换,否则您将不会再次访问它,在此示例中不会发生这种情况。
您的算法遗漏了一个贯穿索引子循环的内部循环。尝试在 rearrange
中将 if
替换为 while
:
function rearrange(arr, ind) {
for (var i = 0, len = arr.length; i < len; i++) {
while (ind[i] !== i) {
swap(arr, i, ind[i]);
swap(ind, i, ind[i]);
}
}
}
关于复杂度的注意事项:虽然这是一个双循环,但复杂度并没有改变,因为在每次交换时,一个元素被正确放置,并且每个元素最多被读取两次(一次通过循环,一次通过 for 循环)。
证明说明:我不会在这里对这个算法做一个完整的证明,但我可以提供线索。如果 ind
是一个排列,则所有元素都属于封闭的排列子循环。 while
循环确保您迭代整个循环,for
循环确保您检查每个可能的循环。
关于javascript - 如何在给定目标索引数组的情况下对数组进行就地排序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37724874/