题10

题10

题目

【2010 统考真题】设将 个整数存放到一维数组 中。设计一个在时间和空间两方面都尽可能高效的算法。将 中保存的序列循环左移 个位置,即将 中的数据由 变换为 。要求:

1. 给出算法的基本设计思想。
2. 根据设计思想, 采用 C 或 C++或 Java 语言描述算法, 关键之处给出注释。
3. 说明你所设计算法的时间复杂度和空间复杂度。

分析

题42
题1

解

1. 算法的基本设计思想:

可将问题视为把数组 转换成数组 ( 代表数组的前 个元素, 代表数组中余下的 个元素),先将 逆置得到 ,再将 逆置得到 ,最后将整个 逆置得到 。设 Reverse 函数执行将数组逆置的操作,对 abcdefgh 向左循环移动 个位置的过程如下:

Reverse(0, p-1) 得到 cbadefgh;

Reverse(p, n-1) 得到 cbahgfed;

Reverse(0, n-1) 得到 defghabc。

注: 在 Reverse 中, 两个参数分别表示数组中待转换元素的始末位置。

2. 使用 语言描述算法如下:

void Reverse(int R[], int from, int to) {
    int i, temp;
    for (i = 0; i < (to - from + 1) / 2; i++) {
        temp = R[from + i];
        R[from + i] = R[to - i];
        R[to - i] = temp;
    }
}
 
void Converse(int R[], int n, int p) {
    Reverse(R, 0, p - 1);
    Reverse(R, p, n - 1);
    Reverse(R, 0, n - 1);
}

3. 上述算法中三个 Reverse 函数的时间复杂度分别为 O(p/2)、O((n-p)/2) 和 O(n/2) ,故所设计的算法的时间复杂度为 O(n) ,空间复杂度为 O(1) 。

【另解】借助辅助数组来实现。算法思想: 创建大小为 p 的辅助数组 S ,将 R 中前 p 个整数依次暂存在 S 中,同时将 R 中后 n-p 个整数左移,然后将 S 中暂存的 p 个数依次放回到 R 中的后续单元。时间复杂度为 O(n) ,空间复杂度为 O(p) 。