PTA（顺序表）2-2 数组循环左移

2-2 数组循环左移

分数 6

作者 DS课程组

单位 浙江大学

本题要求实现一个对数组进行循环左移的简单函数：一个数组a中存有n（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向左移m（≥0）个位置，即将a中的数据由（a0a1⋯a**n−1）变换为（a**m⋯a**n−1a0a1⋯a**m−1）（最前面的m个数循环移至最后面的m个位置）。如果还需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

输入格式:

输入第1行给出正整数n（≤100）和整数m（≥0）；第2行给出n个整数，其间以空格分隔。

输出格式:

在一行中输出循环左移m位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

输入样例：

1
2
8 3
1 2 3 4 5 6 7 8

输出样例：

1
4 5 6 7 8 1 2 3

我的答案（虽然是对的，但是有更好的，见后面）

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
using namespace std;

// 定义顺序表结构
typedef struct {
    int *data;
    int length;
} sqList;

// 初始化顺序表
void initList(sqList &L, int x) {
    L.data = new int[x];
    L.length = 0;
}

// 左移顺序表m个
void moveList(sqList &L, int m, int n) {
    // 先把前m个移至顺序表尾部
    for (int i = 0; i < m; ++i) {
        L.data[L.length] = L.data[i];
        L.length++;
    }
    // 再把第m+1后面的元素挪至最前
    for (int i = 0; i < n; ++i) {
        L.data[i] = L.data[m];
        m++;
    }
    L.length = n; // 顺序表长度变为n
}

int main() {
    int n, m;
    cin >> n >> m; // 读取数组中元素的个数n，和左移数m
    m = m % n;
    sqList L;
    initList(L, m+n); // 顺序表初始化
    // 将读取的数据放入顺序表
    for (int i = 0; i < n; ++i) {
        cin >> L.data[i];
        L.length++;
    }
    // 将数组左移m个
    moveList(L, m, n);

    // 输出移动后的顺序表
    for (int i = 0; i < n; ++i) {
        if (i != 0) {
            cout << " ";
        }
        cout << L.data[i];
    }
}

思路核心是 “借助额外空间暂存前 m 个元素，再移动剩余元素”，整体逻辑能实现数组循环左移，但存在空间利用冗余和潜在逻辑漏洞，以下是思路总结、问题分析及优化建议：

一、核心思路总结

  1. 空间设计：初始化长度为 m+n 的顺序表，用额外的 m 个空间暂存左移时要 “挪到末尾” 的前 m 个元素。
  2. 两步移动：
    • 第一步：把原数组前 m 个元素复制到顺序表的 “额外空间”（即从下标 n 开始的位置），避免被后续元素覆盖。
    • 第二步：把原数组中从 m 开始的剩余元素（共 n-m 个）向前移动，覆盖前 n-m 个位置。
  3. 结果整理：调整顺序表长度为 n，最终前 n 个位置就是左移后的结果。

二、当前思路的问题分析

空间冗余，不符合 “不允许使用另外数组” 的隐含要求

题目明确提到 “不允许使用另外数组”，核心是尽量减少额外空间（理想为 O (1) 空间）。你的方案用了 m 个额外空间（顺序表长度 m+n），虽然没单独建数组，但仍属于 “额外空间存储”，不符合最优空间设计。

三、优化方向（O (1) 空间，更少移动次数）

题目还要求 “移动数据的次数尽量少”，推荐用 “三次反转法”，无需额外空间，且移动次数仅为 O (n)，是最优方案：

  1. 原理：循环左移 m 位，等价于 “反转前 m 个元素 → 反转剩余 n-m 个元素 → 反转整个数组”。
    • 示例（输入n=8, m=3，数组[1,2,3,4,5,6,7,8]）：
      1. 反转前 3 个：[3,2,1,4,5,6,7,8]
      2. 反转剩余 5 个：[3,2,1,8,7,6,5,4]
      3. 反转整个数组：[4,5,6,7,8,1,2,3]（最终结果）
  2. 优化后代码示例：
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
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
using namespace std;

// 反转数组从left到right的元素（闭区间）
void reverse(int arr[], int left, int right) {
    while (left < right) {
        // 交换两个元素，移动次数更少
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}

// 循环左移：O(1)空间，O(n)移动次数
void leftShift(int arr[], int n, int m) {
    if (n == 0 || m % n == 0) return; // 无需移动的情况
    m = m % n; // 处理m >=n 的情况
    reverse(arr, 0, m-1);    // 反转前m个
    reverse(arr, m, n-1);    // 反转剩余n-m个
    reverse(arr, 0, n-1);    // 反转整个数组
}

int main() {
    int n, m;
    cin >> n >> m;
    int arr[n]; // 此处用VLA仅为简化，标准C++建议用vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    leftShift(arr, n, m);
    // 输出（无多余空格）
    for (int i = 0; i < n; ++i) {
        if (i != 0) cout << " ";
        cout << arr[i];
    }
    return 0;
}

四、总结

你的原始思路 “暂存 + 覆盖” 能实现功能，但存在空间冗余和越界风险；优化后的 “三次反转法” 更贴合题目 “不额外用数组” 和 “移动次数少” 的要求，是更优的解决方案。