问题描述
存在一个由n个元素组成的序列R(X0, X1, X2, ..., Xn-2, Xn-1),将R中的元素循环左移p(0<p<n)个位置，即移动后R中的数据为: (Xp, Xp+1, ..., Xn-1, X0, X1, ..., Xp-1)。
简言之，R中的每一个元素都左移p个位置，移动后超出左边界的元素依次放在序列末尾。
序列左移
上图中每一个元素都左移了2 (p为2)个位置，其中A、B移动到了末尾.
解题思想
解法一
- 先存储前p个元素
- 从第p+1个元素开始，依次向前移动p个位置
- 将步骤1存储的p个元素复制到序列R末尾
时间复杂度为O(n)，空间复杂度为 O(p)
解法二
- 翻转整个序列R，范围为[0, n)
- 翻转前n-p个元素，范围为[0, n-p)
- 翻转后n个元素，范围为[n-p, n)
例如有7个元素的序列R为: ABCDEFG，若要左移2个位置
n = 7，p = 2
reverse(0, n); // GFEDCBA
reverse(0, n-p); // CDEFGBA
reverse(n-p, n); // CDEFGAB
该算法时间复杂度为O(n)，空间复杂度为 O(1)
c++实现
这里实现解法二，并结合C++ STL中的reverse函数，要使用reverse函数记得引入<algorithm>头文件
#include <iostream>
#include <algorithm>
void leftOffset(char* R, int n, int p)
{
std::reverse(R, R + n); // 翻转 [0, n)
std::reverse(R, R + (n - p)); // 翻转[0, n-p)
std::reverse(R + (n - p), R + n); // 翻转 [n-p, n)
}
int main()
{
int n = 7;
int p = 2;
char R[] = "ABCDEFG";
leftOffset(R, n, p);
std::cout << R << std::endl;
return 0;
}
拓展
问题:
一位数组A[m+n]中依次存放了两个顺序表(a1, a2, ..., am)和(b1, b2, ..., bn)，使用空间复杂度为O(1)的算法互换两个顺序表的位置，即把(b1, b2, ..., bn)放在(a1, a2, ..., am)的前面。
解法
- 翻转整个数组A，范围为[0, m+n)
- 翻转前n个元素，范围为[0, n)
- 翻转后m个元素，范围为[n, m + n)
时间复杂度为O(n)，空间复杂度为O(1)
本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明: 作者staneyffer，首发于我的博客，原文链接: https://chengfy.com/post/5
