数据结构——第二章线性表·2010真题

MiracleWolf 2024-2-3 129 2/3

一、题目描述

    将一个n(n>1)个整数存放到一维数组R中、设计一个在时间和空间上都尽可能高效的算法,将R中保存的序列循环左移p(0

二、代码实现

首先循环左移p位后新下标的位置为(原下标为i):((i-p)+n)%n,其中n为原数组长度。
0 1 2 3 4 5 6
1 2 3 4 5 6 7 ,循环左移3位:
4 5 6 7 1 2 3 ,原下标为0循环左移3位:((0-3)+7)%7=4,因此下标为4。
接着再开辟一个数组,存放循环后的序列,最后打印即可。相关代码如下:

#include <iostream>
using namespace std;
const int N = 10;
int n, p;
int a[N],b[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) { cin >> a[i]; }
    cin >> p;
    if (p >= n) { cout << "请输入小于n的p值\n"; }
    for (int i = 0; i < n; i++)
    {
        int m=((i - p) + n) % n;//获取新下标值
        b[m] = a[i];//将原来的数放在新下标位置
    }
    for (int i = 0; i < n; i++) { cout << b[i]<<" "; }

    return 0;
}

显然该算法的时间复杂度和空间复杂度均为O(N);

三、总结

本题较为简单,注意循环左移后新下标与原下标的对应关系是:
m=((i-p)+n)%n

- THE END -

MiracleWolf

2月03日15:52

最后修改:2024年2月3日
0