Блог

Эта задача требует, чтобы вы нашли минимальное количество замен, чтобы отсортировать массив перемешанных последовательных цифр в порядке возрастания. Пока что мой код проходит большинство тестов, однако есть четыре, которые завершаются неудачей из-за тайм-аута. Кто-нибудь может объяснить, почему у моего кода истекает время ожидания? Есть ли способ заставить его быстрее находить ответ?

 function minimumSwaps(arr) {
const min = Math.min(...arr);
let swapCount = 0;
const swap = (array, a, b) => {
    let test = array[a];
    array[a] = array[b];
    array[b] = test;
}
for(let i=0; i<arr.length; i  ){
    if(arr[i]!==i min){
        swap(arr, i, arr.indexOf(i min));
        swapCount  ;
    }
}
return swapCount;
}
  

Я подумал, что это хорошее решение, поскольку ему нужно выполнить итерацию по длине массива только один раз? Я хотел бы иметь возможность понять, почему это работает недостаточно хорошо

Ваша большая проблема связана с вызовом arr.indexOf , поскольку он должен сканировать весь массив каждый раз, когда вы выполняете обмен. Вы можете обойти это, сгенерировав обратный поиск из значения в индекс массива перед началом сортировки, а затем сохранив этот список во время сортировки. Обратите внимание, что вам не нужно выполнять полную замену, просто скопируйте значение из arr[i] в его правильное место в массиве, поскольку вы не возвращаетесь к числу после его передачи. Также вам не нужно min , так как по условиям вопроса оно гарантированно равно 1, и вам не нужно смотреть на последнее значение в массиве, поскольку к тому времени, когда вы до него доберетесь, оно должно быть правильным.

 function minimumSwaps(arr) {
  const indexes = arr.reduce((c, v, i) => (c[v] = i, c), []);
  const len = arr.length - 1;
  let swapCount = 0;
  for (let i = 0; i < len; i  ) {
    if (arr[i] !== i   1) {
      arr[indexes[i 1]] = arr[i];
      indexes[arr[i]] = indexes[i 1];
      swapCount  ;
    }
  }
  return swapCount;
}

console.log(minimumSwaps([7, 1, 3, 2, 4, 5, 6]));
console.log(minimumSwaps([4, 3, 1, 2]));
console.log(minimumSwaps([2, 3, 4, 1, 5]));
console.log(minimumSwaps([1, 3, 5, 2, 4, 6, 7]));  

Я думаю, мы должны перевернуть функцию, а не функцию поиска.

 function minimumSwaps($arr) {
$outp = 0;
$result = array_flip($arr);
for($i=0; $i<count($arr); $i  ){
   if($arr[$i] != $i  1){
        $keyswp = $result[$i   1];
        $temp = $arr[$i];
        $arr[$i] = $i   1;
        $arr[$keyswp] = $temp; 
        $tempr = $result[$i   1];
        $result[$i   1] = $i  1;
        $result[$temp] = $keyswp;
        $outp = $outp   1;
    } 
}
return $outp;     
  

}

Вот мое решение, оно похоже на решение Nick , за исключением того, что вместо массива.Метод Proptytype.indexOf Я использовал объектный литерал для сопоставления индексов каждого значения для лучшей временной сложности, поскольку поиск в объектном литерале равен O (1) (вы также можете использовать карты ES6). Вот код

 function minimumSwaps(arr) {
    
    let count = 0;
    let search = arr.reduce((o, e, i) => {
        o[e] = i
        return o
    }, {})
    
    

    for(let i =0 ; i < arr.length - 1; i  ){
        let j = search[i 1]
        
        if(arr[i] !== i 1) {
            [arr[i], arr[j]] = [arr[j], arr[i]]
            
            search[arr[i]] = i;
            search[arr[j]] = j;
            count  = 1
        }
        
    }
    
    console.log(arr)
    return count
} 
  

Как предлагали другие, вам не следует использовать indexOf метод, поскольку он создает ваше решение O(n^2) (поскольку indexOf метод должен снова сканировать весь массив). Вы можете заранее создать массив карт позиций и использовать его позже во время обмена. Это сохранит линейность вашего решения. Вот подробное объяснение и решение проблемы минимальной замены 2 HackerRank в java, c, c и js с использованием этого метода.