文章
58
粉丝
253
获赞
1
访问
22.0k
### (1)算法基本设计思想
采用**三次反转法**,该方法在时间和空间效率上均最优,核心思路如下:
1. **分割序列**:将数组 `R` 按左移位数 `P` 分为两部分——左段 `A = [X0, X1, ..., Xp-1]`(长度 `P`)和右段 `B = [Xp, Xp+1, ..., Xn-1]`(长度 `n-P`);
2. **三次反转**:
- 反转左段 `A`,得到 `A' = [Xp-1, ..., X1, X0]`;
- 反转右段 `B`,得到 `B' = [Xn-1, ..., Xp+1, Xp]`;
- 反转整个数组(`A' + B'`),最终得到目标序列 `[Xp, ..., Xn-1, X0, ..., Xp-1]`。
本质是通过“局部反转+整体反转”的组合,避免额外存储空间消耗,同时保证线性时间复杂度。
### (2)C语言实现(关键注释)
```c
#include <stdio.h>
// 辅助函数:反转数组从下标left到right的元素(闭区间)
void reverse(int R[], int left, int right) {
while (left < right) {
// 交换left和right位置的元素
int temp = R[left];
R[left] = R[right];
R[right] = temp;
// 向中间靠拢
left++;
right--;
}
}
// 主函数:循环左移P个位置
void leftRotate(int R[], int n, int P) {
// 处理P≥n的情况(左移n位等价于不移动,故取模简化)
P = P % n;
if (P == 0) return; // 移动0位,直接返回
// 1. 反转左段:[0, P-1]
reverse(R, 0, P-1);
// 2. 反转右段:[P, n-1]
reve...
登录后发布评论
暂无评论,来抢沙发