AC102-数组循环左移¶

将 n 个整数存放在数组 R 中，设计尽可能高效的算法，将 R 序列循环左移 p 个位置（0 < p < n），即将 R 中的数据由 (X₀, X₁, ..., Xₙ₋₁) 变换为 (Xₚ, Xₚ₊₁, ..., Xₙ₋₁, X₀, X₁, ..., Xₚ₋₁)。（2010 年统考题）

切片为AB33

代码实现¶

C
/**
 * 反转数组的指定区间
 * @param R[] 待处理数组
 * @param start 区间起始索引（包含）
 * @param end   区间结束索引（包含）
 */
void Reverse(int R[], int start, int end) {
    // 双指针法反转数组区间
    while (start < end) {
        // 交换两端元素
        int temp = R[start];
        R[start] = R[end];
        R[end] = temp;

        // 移动指针
        start++;
        end--;
    }
}

/**
 * 数组循环左移 p 个位置
 * @param R[] 待处理数组
 * @param n   数组长度
 * @param p   左移的位置数（0 < p < n）
 */
void change(int R[], int n, int p) {
    // 第一步：整体反转整个数组
    Reverse(R, 0, n - 1);

    // 第二步：反转前 n-p 个元素
    Reverse(R, 0, n - p - 1);

    // 第三步：反转后 p 个元素
    Reverse(R, n - p, n - 1);
}

算法执行过程图解¶

假设 n=8，p=3，初始数组为 [X0, X1, X2, X3, X4, X5, X6, X7]

初始状态：¶

Text Only
1	`[X0, X1, X2, X3, X4, X5, X6, X7]`

第一步：整体反转¶

调用 Reverse(R, 0, 7) 后：

Text Only
1	`[X7, X6, X5, X4, X3, X2, X1, X0]`

第二步：反转前 n-p 个元素¶

调用 Reverse(R, 0, 4) 后：

Text Only
1	`[X3, X4, X5, X6, X7, X2, X1, X0]`

第三步：反转后 p 个元素¶

调用 Reverse(R, 5, 7) 后：

Text Only
1	`[X3, X4, X5, X6, X7, X0, X1, X2]`

最终结果即为循环左移 p 个位置后的数组。

复杂度分析¶

时间复杂度：O(n)¶

详细分析：

第一次反转：
反转整个数组，操作次数为 n/2
时间复杂度 O(n)
第二次反转：
反转前 n-p 个元素，操作次数为 (n-p)/2
时间复杂度 O(n-p)
第三次反转：
反转后 p 个元素，操作次数为 p/2
时间复杂度 O(p)

总时间复杂度：

Text Only
1 2	`T(n) = O(n/2) + O((n-p)/2) + O(p/2) = O(n)`

空间复杂度：O(1)¶

只使用了常数个额外变量（start, end, temp）
原地操作，不需要额外的存储空间
空间复杂度为 O(1)

算法原理深入解析¶

1. 反转操作的数学基础¶

重要性质：¶

对一个序列进行两次完全反转可以恢复原序列
反转操作具有可逆性

数学推导：¶

设原始序列为 S = [X0, X1, ..., Xn-1]

整体反转：

Text Only
1	`Reverse(S, 0, n-1) → [Xn-1, Xn-2, ..., X0]`

分段反转：

前 n-p 个元素反转：

Text Only
1	`Reverse([Xn-1, ..., Xp], 0, n-p-1) → [Xp, Xp+1, ..., Xn-1]`

后 p 个元素反转：

Text Only
1	`Reverse([Xp-1, ..., X0], n-p, n-1) → [X0, X1, ..., Xp-1]`

组合结果：

Text Only
1	`Final Result = [Xp, Xp+1, ..., Xn-1, X0, X1, ..., Xp-1]`

2. 算法正确性证明¶

性质1：每个元素的最终位置正确¶

元素 Xi (i >= p) 最终位置应为 i-p
元素 Xi (i < p) 最终位置应为 n-p+i

通过三次反转可以验证每个元素都到达了正确位置。

性质2：相对顺序保持不变¶

每次反转都是整体操作，不会改变子序列内部的相对顺序
因此最终结果保持了原始序列的相对顺序

3. 边界情况分析¶

p = 1
整体反转后再分两部分反转
结果正确
p = n-1
实际等价于右移 1 位
算法仍能正确处理
p = n/2
特殊情况：正好对半分
算法依然适用

关键知识点延伸¶

1. 原地算法的优势¶

空间效率高：只需 O(1) 额外空间
缓存友好：数据局部性好，访问连续内存
实现简单：只需要基本的交换操作

2. 扩展应用：循环右移¶

C
/**
 * 数组循环右移 p 个位置
 * @param R[] 待处理数组
 * @param n   数组长度
 * @param p   右移的位置数（0 < p < n）
 */
void RotateRight(int R[], int n, int p) {
    // 右移 p 位等价于左移 n-p 位
    change(R, n, n - p);
}

3. 通用旋转函数¶

C
/**
 * 数组旋转函数
 * 支持正负方向旋转
 * @param R[] 待处理数组
 * @param n   数组长度
 * @param k   旋转步数（正数表示右移，负数表示左移）
 */
void Rotate(int R[], int n, int k) {
    if (k == 0 || n <= 1) return;  // 无需旋转

    // 处理负数和超过长度的情况
    k %= n;
    if (k < 0) k += n;  // 转换为正旋转

    // 使用三次反转实现旋转
    Reverse(R, 0, n - 1);      // 整体反转
    Reverse(R, 0, k - 1);      // 反转前 k 个
    Reverse(R, k, n - 1);      // 反转后 n-k 个
}

4. 分块移动法实现¶

C
/**
 * 分块移动法实现循环左移
 * 适用于无法使用反转的情况
 */
void BlockSwapLeftShift(int R[], int n, int p) {
    int i = p, j = n - p;

    while (i != j) {
        if (i < j) {
            // 将后部分的前 i 个元素与前部分交换
            for (int k = 0; k < i; k++) {
                swap(&R[p-i+k], &R[p+j-i+k]);
            }
            j -= i;
        } else {
            // 将前部分的后 j 个元素与后部分交换
            for (int k = 0; k < j; k++) {
                swap(&R[p-j+k], &R[p-i+j+k]);
            }
            i -= j;
        }
    }

    // 最后一次交换
    for (int k = 0; k < i; k++) {
        swap(&R[p-i+k], &R[p+j-i+k]);
    }
}

5. 应用场景¶

字符串处理：循环移位加密、文本处理
图像处理：像素矩阵旋转
数据缓冲区管理：循环队列实现
多媒体处理：音频视频帧的循环移动

算法特点总结¶

高效性：时间复杂度 O(n)，空间复杂度 O(1)
通用性：可以通过参数调整实现左右任意方向的旋转
稳定性：保持元素的相对顺序不变
简洁性：实现简单，逻辑清晰
可靠性：适用于各种边界情况

记忆要点¶

三次反转法：整体反转 + 分段反转
反转顺序：先整体，再前段，最后后段
时间复杂度：线性时间 O(n)
空间复杂度：原地操作 O(1)
扩展性：可通过调整参数实现左右旋转