【算法笔记】序列循环左（右）移

问题描述

存在一个由n个元素组成的序列R(X₀, X₁, X₂, ..., X_n-2, X_n-1),将R中的元素循环左移p(0<p<n)个位置，即移动后R中的数据为: (X_p, X_p+1, ..., X_n-1, X₀, X₁, ..., X_p-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]中依次存放了两个顺序表(a₁, a₂, ..., a_m)和(b₁, b₂, ..., b_n)，使用空间复杂度为O(1)的算法互换两个顺序表的位置，即把(b₁, b₂, ..., b_n)放在(a₁, a₂, ..., a_m)的前面。
解法

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