В этой задаче нам предлагается повернуть массив целых чисел на заданное количество шагов. Хотя поиск наиболее оптимизированного решения кажется простым, для большинства из нас он может оказаться захватывающей головоломкой.

В этой статье мы рассмотрим несколько различных подходов к решению этой проблемы. Мы начнем с обсуждения подхода грубой силы, который обеспечивает простое, но наивное решение. Оттуда мы будем двигаться к более оптимизированным методам, которые улучшают как временную, так и пространственную сложность. Но перед этим мы увидим постановку задачи.

Постановка проблемы:

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

Следите за обновлениями в следующих разделах, где мы рассмотрим различные подходы к решению этой проблемы.

Подход 1: грубая сила

Подход заключается в выполнении поворота в цикле на заданное количество шагов, сдвигая каждый элемент на одну позицию вправо.

  1. В этом подходе мы перебираем массив k раза.
  2. На каждой итерации мы сдвигаем каждый элемент на одну позицию вправо, заменяя текущий элемент элементом перед ним.
  3. Последний элемент сохраняется в переменной lastElement перед началом процесса сдвига, а затем присваивается первой позиции nums[0] в конце каждой итерации.
  4. Этот процесс фактически поворачивает массив на k шагов вправо.
// ES6 Arrow Function
const rotateArray = (nums, k) => {
    const n = nums.length;
    k = k % n;

    for(let i = 0; i < k; i++) {
        const last = nums[n - 1];
        for(let j = n - 1; j > 0; j--) {
            nums[j] = nums[j-1];
        }

        nums[0] = last;
    }

    return nums;
}

Временная сложность:O(K * N)

Поскольку мы итерируем массив k раз, и на каждой итерации он сдвигает каждый элемент на одну позицию вправо. Здесь N — длина массива.

Пространственная сложность:O(1)

Поскольку он выполняет вращение на месте без использования каких-либо дополнительных структур данных, следовательно, сложность пространства постоянна.

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

Подход 2. Использование дополнительного пространства

Другой подход предполагает использование дополнительного массива для хранения повернутых элементов. Мы копируем последние k элементов исходного массива в начало нового массива, а затем оставшиеся элементы из исходного массива.

  1. Поэтому мы создаем новый массив rotatedArray для хранения повернутых элементов.
  2. Копируем последние k элементов исходного массива в начало rotatedArray.
  3. Затем мы копируем оставшиеся элементы из исходного массива.
  4. Верните rotatedArray.
// ES6 Arrow Function
const rotateArray = (nums, k) => {
    const n = nums.length;
    k = k % n;

    const rotatedArray = [];

    for(let i = n - k; i < n; i++) {
        rotatedArray.push(nums[i]);
    }

    for(let i = 0; i < n - k; i++) {
        rotatedArray.push(nums[i]);
    }

    return rotatedArray;
}

Временная сложность:O(N)

Алгоритм выполняет итерацию по входному массиву один раз, чтобы скопировать элементы в rotatedArray. Следовательно, временная сложность равна O(n), где N — размер массива.

Пространственная сложность:O(N)

Здесь создается новый массив для хранения повернутых элементов, и размер этого массива равен размеру входного массива. Таким образом, пространственная сложность равна O(N), так как для этого требуется дополнительное пространство, пропорциональное размеру входных данных.

Подход 3: реверсивный массив

Это оптимизированный подход к решению этой проблемы. Он включает в себя обращение всего массива, за которым следует обращение первых k элементов и оставшихся n-k элементов по отдельности. Такой подход позволяет добиться желаемого поворота на месте без использования дополнительного пространства.

  1. Мы определяем функцию, которая переворачивает массив, используя индексы start и end, указанные в аргументах.
  2. Во-первых, мы переворачиваем весь входной массив.
  3. Затем мы обращаем первые k элементов в обращенном массиве.
  4. Наконец, мы обращаем оставшиеся n-k элементов в обращенном массиве.
// ES6 Arrow Function
const reverseArray = (arr, start, end) => {
    while(start < end) {
        [arr[start], arr[end]] = [arr[end], arr[start]]; 
        start++;
        end--;
    }
}

const rotateArray = (nums, k) => {
    const n = nums.length;
    k = k % n;

    reverseArray(nums, 0, n-1);
    reverseArray(nums, 0, k-1);
    reverseArray(nums, k, n-1);

    return nums;
}

Временная сложность:O(N)

В заданном входном массиве есть три обратные операции над подмассивами. Мы обращаем массив, используя функцию reverseArray, и временная сложность этой функции составляет O (N). Следовательно, общая временная сложность функции rotateArray является линейной.

Пространственная сложность:O(1)

Поскольку поворот происходит на месте, не занимая дополнительного места, и мы возвращаем один и тот же массив, сложность пространства постоянна.

Важный:

Почему K = k % n, где n – длина входного массива.

Для обработки случаев, когда значение k больше или равно размеру массива n. Поскольку поворот массива по его размеру или кратному его размеру приводит к тому же самому массиву, нет необходимости выполнять избыточные повороты. Цель k = k % n состоит в том, чтобы убедиться, что k находится в пределах допустимого диапазона поворотов.

Выполняя операцию по модулю (%) с n, мы уменьшаем k до эквивалентного числа оборотов, попадающих в пределы массива. Этот шаг эффективно приводит k к значению от 0 до n-1, гарантируя, что оно представляет правильное количество оборотов, необходимое для заданного размера массива.

Например, если массив имеет длину 5 (n = 5), а k равно 7, операция по модулю k = k % n установит k в 2. Это означает, что поворот массива на 7 шагов эквивалентен повороту его на 2 шага в пределах размера массива. . Эта корректировка помогает оптимизировать решение и позволяет избежать ненужных поворотов.

Включение k = k % n в код гарантирует, что решения работают правильно для любого значения k, даже если оно превышает размер массива.

И у вас есть это, ребята! Мы исследовали различные подходы, оптимизировали наши решения и, надеюсь, повеселились. Я надеюсь, что эта статья предоставила вам ценную информацию и помогла лучше понять различные подходы к решению этой проблемы. Удачного кодирования!

Проблема: Литкод 189