算法笔记 --序列循环左(右)移

问题描述

存在一个由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移动到了末尾.

解题思想

解法一

  1. 先存储前p个元素
  2. 从第p+1个元素开始,依次向前移动p个位置
  3. 将步骤1存储的p个元素复制到序列R末尾

时间复杂度为O(n),空间复杂度为 O(p)

解法二

  1. 翻转整个序列R,范围为[0, n)
  2. 翻转前n-p个元素,范围为[0, n-p)
  3. 翻转后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)的前面。
解法

  1. 翻转整个数组A,范围为[0, m+n)
  2. 翻转前n个元素,范围为[0, n)
  3. 翻转后m个元素,范围为[n, m + n)

时间复杂度为O(n),空间复杂度为O(1)


本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明: 作者staneyffer,首发于我的博客,原文链接: https://chengfy.com/post/5


载入评论中....