给定一个大小为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
这里我们将讨论另一种方法,该方法使用反转数组的一部分的概念。这个想法背后的直觉如下:
如果我们仔细观察,我们可以看到一组数组元素正在改变其位置。例如,以下数组:
arr[] = {1, 2, 3, 4, 5, 6, 7}
和 d = 2 。
旋转后的数组为 {3, 4, 5, 6, 7, 1, 2}
具有前两个元素的组正在移动到数组的末尾。这就像颠倒数组一样。
所以操作顺序是:
当我们执行反向操作时,它也类似于以下顺序:
该算法可以借助以下伪代码进行描述:
算法反向(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程序用于数组旋转的逆向算法
#函数将 []从索引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)
3 4 5 6 7 1 2
时间复杂度: O(N) 辅助空间: O(1)
使用 C++ STL 逆向
#将数组向右旋转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= " ");
4 5 1 2 3
时间复杂度:O(N) 辅助空间:O(1)