Лучше / быстрее алгоритм вращения массива?

Question

Для данного массива поверните массив вправо на k шагов, где k неотрицательно.

Пример 1:

Вход: [1,2,3,4,5,6,7] и k = 3

Выход: [5,6,7,1 , 2,3,4]

Объяснение:

Шаг 1: [7,1,2,3,4,5,6]

Шаг 2: [6,7,1,2,3,4,5]

Шаг 3: [5,6,7,1,2,3,4]

My Решение:

var rotate = function(nums, k) {
while(k>0){ 
 let lastelm = nums[nums.length-1];
  for(let i =nums.length; i>0;i--){
    temp = nums[i-1];
    nums[i-1] = nums[i-2];    
  }
  nums[0]=lastelm
  k--;
 }     
};

Я думаю, что мое решение O (k * nums.length)

Я изменяю весь массив столько раз, сколько k

Что может быть лучший подход к этому?

Answer 1

Вы можете использовать .slice, чтобы извлечь два массива из массива - один, начинающийся с начала, заканчивающийся в середине, а другой, начинающийся в середине и заканчивающийся в конце. Затем просто объедините их в обратном порядке:

const rotate = (nums, k) => [...nums.slice(-k), ...nums.slice(0, -k)];
console.log(rotate([1,2,3,4,5,6,7], 1));
console.log(rotate([1,2,3,4,5,6,7], 3));

Если у вас есть для изменения существующего массива, то:

const rotate = (nums, k) => {
  const moveAfter = new Array(k).concat(nums.slice(0, -k));
  Object.assign(nums, nums.slice(-k), moveAfter);
  return nums;
};
console.log(rotate([1,2,3,4,5,6,7], 1));
console.log(rotate([1,2,3,4,5,6,7], 3));

Если k может быть больше, чем длина массива, сначала используйте модуль по нему:

const rotate = (nums, kPossiblyOutOfRange) => {
  const k = kPossiblyOutOfRange % nums.length;
  return [...nums.slice(-k), ...nums.slice(0, -k)];
}
console.log(rotate([1,2,3,4,5,6,7], 1));
console.log(rotate([1,2,3,4,5,6,7], 8));
console.log(rotate([1,2,3,4,5,6,7], 3));

Answer 2

Самый простой способ сделать это - просто отслеживать сдвиг при чтении или записи в массив. Т.е. сохраняют постоянное значение 'shift', а когда вы читаете или пишете из массива по индексу i, вносите корректировку в (i + shift)% (размер массива).

Answer 3

unshift в сочетании с pop , кажется, делает трюк:

var rotate = function(nums, k) {
    while (k > 0) { 
        nums.unshift(nums.pop());
        k--;
    }
}