¿Cómo ordenar una matriz en el lugar dada una matriz de índices de destino?
¿Cómo ordenarías una matriz dada?arr
en su lugar dado un conjunto de índices objetivoind
?
Por ejemplo:
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"]
Intenté el siguiente algoritmo, pero falla en el segundo ejemplo anterior.
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]);
}
}
}
¿Cómo resolverías esto en O (n) tiempo y O (1) espacio extra?
¿Podría proporcionar una prueba de que su algoritmo funciona?
Nota: Esta pregunta se parece aéste, pero aquí mutandoind
esta permitido.