A Solution of A Written Question in An Examination (2)

Posted on

Question

设计一个算法，将数组A[n]中的元素A[0]至A[n-1]循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换次数为O(n)。

Solution

对于要求只有一个元素大小的附加存储的循环右移，可以分为以下3步进行：

  • 1 对所有n个元素逆序；
  • 2 对前k个元素逆序；
  • 3 对后n-k个元素逆序。

由于逆序可以只占用一个元素大小，元素交换次数为O(n)，该算法可以满足题目要求。

算法的C语言实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void rotateRight(int* A, int n, int k)
// A为给定数组，n为数组大小，k为指定的移动位数
{
	int temp; //附加存储
	k = k % n;
	// n个元素逆序
	for(int i = 0; i < n / 2; i++)
	{
		temp = A[i];
		A[i] = A[n - 1 - i];
		A[n - 1 - i] = temp;
	}
	// 前k位逆序
	for(int i = 0; i < k / 2; i++)
	{
		temp = A[i]; 
		A[i] = A[k - 1 - i];
		A[k - 1 - i] = temp;
	}
	// 后n-k位逆序
	for(int i = 0; i < (n - k) / 2; i++)
	{
		temp = A[i + k];
		A[i + k] = A[n - 1 - i];
		A[n - 1 - i] = temp;
	}
	return;
}