小白学算法-数据结构和算法教程: 数组旋转的反转算法

用户1418987

发布于 2023-10-26 14:15:24

1530

发布于 2023-10-26 14:15:24

文章被收录于专栏：coder

数组旋转的反转算法

给定一个大小为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

＃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 逆向

Python 代码

＃将数组向右旋转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= " ");