Вращение массива — распространенная операция в программировании, при которой элементы массива циклически сдвигаются вправо или влево. В этой статье блога мы рассмотрим различные методы эффективного выполнения циклического вращения массива в C++. Мы предоставим примеры кода для каждого метода и обсудим их временные и пространственные сложности. Давайте погрузимся!

Метод 1: метод грубой силы
Простейший подход к циклическому вращению массива предполагает сдвиг элементов один за другим в цикле. Вот фрагмент кода:

void rotateArray(int arr[], int n, int k) {
    for (int i = 0; i < k; i++) {
        int temp = arr[n - 1];
        for (int j = n - 1; j > 0; j--) {
            arr[j] = arr[j - 1];
        }
        arr[0] = temp;
    }
}

Временная сложность: O(n * k)
Пространственная сложность: O(1)

Метод 2: использование дополнительного массива
Другой подход заключается в создании нового массива и копировании элементов из исходного массива на основе желаемого поворота. Вот пример:

void rotateArray(int arr[], int n, int k) {
    int rotatedArray[n];
    for (int i = 0; i < n; i++) {
        rotatedArray[(i + k) % n] = arr[i];
    }
    for (int i = 0; i < n; i++) {
        arr[i] = rotatedArray[i];
    }
}

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

Метод 3: использование техники реверса
Этот метод включает в себя переворот массива в три этапа: перевернуть весь массив, перевернуть первые k элементов и, наконец, перевернуть оставшиеся элементы. Вот код:

void reverseArray(int arr[], int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}
void rotateArray(int arr[], int n, int k) {
    k = k % n;
    reverseArray(arr, 0, n - 1);
    reverseArray(arr, 0, k - 1);
    reverseArray(arr, k, n - 1);
}

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

Метод 4. Использование std::rotate
C++ предоставляет функцию std::rotateв библиотеке , которая эффективно выполняет вращение массива. Вот пример:

#include <algorithm>
void rotateArray(int arr[], int n, int k) {
    std::rotate(arr, arr + k, arr + n);
}

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

В этой статье мы рассмотрели несколько методов выполнения циклического вращения массива в C++. Эти методы включают в себя метод грубой силы, использование дополнительного массива, обратную технику и использование функции std::rotate. Каждый метод имеет свои преимущества и сложности, поэтому выбор метода зависит от таких факторов, как размер массива, количество оборотов и требования к производительности. Понимая эти методы, вы сможете эффективно решать задачи вращения массивов в своих программах на C++.