数组旋转的反转算法
给定一个大小为N的数组 arr[]，任务是将数组向左旋转d 个位置。
例子
输入： 输出： 3, 4, 5, 6, 7, 1, 2 解释：如果数组旋转 1 个位置向左， 变为{2, 3, 4, 5, 6, 7, 1}。 再旋转1个位置 就变成：{3, 4, 5, 6, 7, 1, 2} 输入： arr[] = {1, 6, 7, 8}, d = 3 输出： 8, 1, 6, 7
方法 1：讨论的方法有：
- 使用另一个临时数组。
- 一一旋转。
- 使用复杂算法。
另一种方法（反转算法）：
这里我们将讨论另一种方法，该方法使用反转数组的一部分的概念。这个想法背后的直觉如下：
如果我们仔细观察，我们可以看到一组数组元素正在改变其位置。例如，以下数组：
arr[] = {1, 2, 3, 4, 5, 6, 7}和 d = 2 。
旋转后的数组为 {3, 4, 5, 6, 7, 1, 2}
具有前两个元素的组正在移动到数组的末尾。这就像颠倒数组一样。
- 但问题是，如果我们只反转数组，它就会变成{7,6,5,4,3,2,1}。
- 旋转后，具有前 5 个元素{7, 6, 5, 4, 3}和后 2 个元素{2, 1} 的块中的元素应按初始数组的实际顺序 [即，{3, 4, 5, 6, 7} 和 {1, 2} ]但这里情况相反。
- 因此，如果再次反转这些块，我们就会得到所需的旋转数组。
所以操作顺序是：
- 反转整个数组
- 然后反转最后一个“d”元素并
- 然后反转第一个（Nd）元素。
当我们执行反向操作时，它也类似于以下顺序：
- 反转第一个 'd' 元素
- 反转最后 (Nd) 元素
- 反转整个数组。
算法：
该算法可以借助以下伪代码进行描述：
伪代码：
算法反向(arr, start, end): mid = (start end)/2 从i = start到mid循环: swap (arr[i], arr[end-(mid-i 1)]) 算法旋转（arr，d，N）： 反向（arr，1，d）； 反向(arr, d 1, N); 反向（arr，1，N）；
插图：
请按照下图更好地理解算法：
例如，采用数组arr[] = {1, 2, 3, 4, 5, 6, 7}和d = 2。
大批 旋转后的数组将如下所示：
旋转阵列 第一步：将数组视为两个块的组合。一个包含前两个元素，另一个包含其余元素，如上所示。
考虑2块 第二步：现在反转前d个元素。就变成如图所示了
反转前 K 个元素 第三步：现在反转最后（Nd）个元素。就变成如下图所示：
反转最后 (NK) 个元素 第四步：现在数组与左移d次后的数组完全相反。因此，反转整个数组，您将得到所需的旋转数组。
总数组反转 看到该数组现在与旋转后的数组相同。
代码实现
Python
代码语言：javascript复制＃Python程序用于数组旋转的逆向算法
＃函数将 []从索引start到end反转
def reverseArray(arr, start, end):
while (start < end):
temp = arr[start]
arr[start] = arr[end]
arr[end] = temp
start = 1
end = end-1
＃通过d将大小为n的arr[]向左旋转的函数
def leftRotate(arr, d):
if d == 0:
return
n = len(arr)
# 如果旋转因子大于阵列长度
d = d % n
reverseArray(arr, 0, d-1)
reverseArray(arr, d, n-1)
reverseArray(arr, 0, n-1)
# 打印数组的函数
def printArray(arr):
for i in range(0, len(arr)):
print (arr[i],end=' ')
＃测试上述函数的驱动程序函数
arr = [1, 2, 3, 4, 5, 6, 7]
n = len(arr)
d = 2
leftRotate(arr, d) # 将数组旋转 2
printArray(arr)输出
代码语言：javascript复制3 4 5 6 7 1 2时间复杂度： O(N) 辅助空间： O(1)
另一种方法：
使用 C STL 逆向
Python 代码
代码语言：javascript复制＃将数组向右旋转k个元素的函数
def rotateArray(arr, k):
＃找到数组的大小
n = len(arr);
# 用数组的大小对 k 取模
# 处理 k 大于数组大小的情况
k %= n;
# 反转整个数组
arr[0:n] = arr[0:n][::-1]
# 反转前 k 个元素
arr[0:k] = arr[0:k][::-1]
# 倒转剩余的 n-k 个元素
arr[k:n] = arr[k:n][::-1]
# 初始化数组
arr = [ 1, 2, 3, 4, 5 ];
# 向右旋转的元素数量
k = 2;
# 调用 rotateArray 函数旋转数组
rotateArray(arr, k);
for i in range(0,len(arr)):
print(arr[i], end= " ");输出
代码语言：javascript复制4 5 1 2 3时间复杂度：O(N) 辅助空间：O(1)
