数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 实现数组右移的反转算法
在本文中，我们将了解如何使用反转算法将给定数组向右旋转 k 个元素，例如 -
Input : arr[ ] = { 4, 6, 2, 6, 43, 7, 3, 7 }, k = 4
Output : { 43, 7, 3, 7, 4, 6, 2, 6 }
Explanation : Rotating each element of array by 4-element to the right gives { 43, 7, 3, 7, 4, 6, 2, 6 }.
Input : arr[ ] = { 8, 5, 8, 2, 1, 4, 9, 3 }, k = 3
Output : { 4, 9, 3, 8, 5, 8, 2, 1 }解决方法
您可以通过将每个元素向右移动并重复此过程 k 次来轻松解决此问题。但是，这将花费更多时间，因为其时间复杂度将为 O(k * N)。
反转算法：反转会反转数组，并且可以通过反转一些元素范围来完成数组旋转。根据此算法 -
- 首先，反转整个数组。
- 使用 k 对 N（数组大小）取模来修改 k，因为 k 大于 N。
- 反转数组的前 k 个元素以使其按顺序排列。
- 然后反转剩余元素的范围，即从 k 到 N-1。
示例
using namespace std;
#include <bits/stdc++.h>
void reverse(int nums[], int start,int end) {
int temp=0;
// reversing array with swapping start element with end element.
while(start<=end){
temp=nums[end];
nums[end]=nums[start];
nums[start]=temp;
start++;
end--;
}
}
int main() {
int arr[] = {4, 6, 2, 6, 43, 7, 3, 6, 2, 4, 5 };
int N = sizeof(arr)/sizeof(arr[0]);
int k = 4;
// reversing whole array
reverse(arr, 0, N-1);
k = k%N;
// reversing element range of 0 to k-1.
reverse(arr, 0, k-1);
// reversing element range of k to last element.
reverse(arr, k, N-1);
cout << "Array after rotating by k-elements : ";
for(int i = 0;i<N;i++)
cout << arr[i] << " ";
return 0;
}输出
Array after rotating by k-elements : 6 2 4 5 4 6 2 6 43 7 3
结论
在本文中，我们讨论了使用反转算法将数组向右旋转 k 个元素的问题。我们讨论了什么是反转算法以及如何实现它来解决此问题。我们还讨论了 C++ 代码来解决此问题。我们可以使用其他任何语言（如 C、Java、Python 等）编写此代码。希望本文对您有所帮助。
更新于： 2021年11月29日
684 次查看
广告