Получив несортированный массив arr[] размером N, поверните его на D элементов (по часовой стрелке).
Если вы это читаете, скорее всего, вы пришли сюда с geeksforgeeks, так как не смогли решить задачу с требуемой временной сложностью. Не волнуйтесь, просто следуйте инструкциям, и я покажу вам и объясню код, который я использовал для этого вопроса.
Код
#include<bits/stdc++.h> using namespace std;
int main(){ int t; cin>>t; while (t>0) { t--; long long n, d; cin>>n>>d; long long arr[n]; for(long long i = 0; i < n; i++){ cin>>arr[i]; } //reversing section of array from starting to point A int start = 0, end = d -1; while (start<end) { swap(arr[start], arr[end]);; start++; end--; } //reversing section of array from point B to end of the array start = d, end = n-1; while (start<end) { swap(arr[start], arr[end]); start++; end--; } //reversing the whole of the array this time. start = 0, end = n-1; while (start<end) { swap(arr[start], arr[end]); start++; end--; } for(int i = 0; i < n; i++){ cout<<arr[i]<<' '; }
cout<<endl; } return 0; }
Объяснение
В качестве примера возьму массив [1, 2, 3, 4, 5]. Теперь предположим, что в массиве есть 2 точки A и B. A - это индексная точка в d-1, а B - в d. Теперь мы предполагаем 2 секции в массиве с помощью этих 2 точек.
- начало массива (от индекса 0) до точки A.
- от точки B до конца массива (n-1).
Алгоритм
- поменять местами элементы массива от начальной точки до точки A.
- поменять местами элементы массива от точки B до конца массива.
- на этот раз поменять местами элементы всего массива.
После первого шага [2, 1, 3, 4, 5] вы получите что-то вроде этого, после второго шага это [2, 1, 5, 4, 3] и после третьего шага [3, 4, 5, 1, 2 ] вы получите такой результат, который также является решением нашего вопроса.
Примечание:-
Мы используем функцию подкачки для замены элементов массива, если вы не знаете о функции подкачки (), то вы можете проверить здесь, чтобы понять, что эта функция подкачки () делает в нашем коде.
Сложность
Временная сложность этого алгоритма составляет O(n). Я не знаю космической сложности, если вы в конечном итоге обнаружите это, дайте мне знать.