gpt4 book ai didi

javascript - 如何通过索引数组重新排列数组(证明)?

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:22:15 27 4
gpt4 key购买 nike

给定数组 arr 和索引数组 ind,以下算法就地重新排列 arr 以满足给定的索引:

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]);
}
}
}

例如:

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"]

证明该算法有效的最有说服力的方法是什么?

最佳答案

这个算法不行,举个反例就够了:

var arr = ["A", "B", "C", "D"];
var ind = [ 2, 3, 1, 0];

rearrange(arr, ind);
console.log(arr); // => ["C", "D", "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]);
if (ind[i] < i) {
i = ind[i]-1;
}
}
}
}

关于javascript - 如何通过索引数组重新排列数组(证明)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37723626/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com