/*
2010
算法思想:
题干要求是左移p格(0<p<n),那么反其道而行之,根据自己的位置推测出哪一个下标的数会被移到自己的位置上。
1、先将下标为0的元素存放在临时变量x上,将工作指针i指向0号元素,i记录当前工作指针所指元素的下标
2、根据j =(i+p) % n 计算出将要移到自己位置上的下标为j的元素
3、将下标为j的元素值移动到下标i处,将工作指针i指向下标j,重复执行2,直到i为(0-p+n) % n时终止(下标0左移p格所处位置)
4、将临时变量x存放的元素移动到j=(0-p+n) % n处,直至完成所有的移动
空间复杂度O(1),时间复杂度O(n)
总结:为了完成原地算法,将第一个需要被移动的元素临时存起来,防止被覆盖,将下一个元素移动到该位置,再将下下一个元素移动下一个元素的位置
逆向思维,依此到第一个被移动元素左移后的位置,直至完成所有的位置互换,而无需额外的存储空间
*/
// 一维数组
const int N = 1e5 + 10;
int data[N];
// 对数组data中的n个元素左移p格
void left_move_n(int p, int n) {
int x = data[0]; // 临时存放第一个元素
int i = 0; // 工作指针指向下标0
while(i != (0 - p + n) % n) { // 循环进行到下标0左移p格后的位置
int j = (i + p + n) % n; // 根据当前位置推算左移p格到当前位置的上一个元素的位置
data[i] = data[j]; // 将上一个元素的值移动到左移后的位置
i = j; // 工作指针跳到上一个元素的位置
}
data[i] = x; // 将临时存放的变量移动到左移p格后的位置
}
方法二
更加模块化,更加简洁易懂,但从时间上来看,比上一个稍微慢一点
// 互换元素
void swap(int &a, int &b) {
int tmp = a; a = b; b = tmp;
}
// 将data数组区间[l, r]进行逆置
void reverse(int data[], int l, int r) {
while(l < r) swap(data[l ++], data[r --]);
}
// n个元素的数组,左移p格
void shift_left(int data[], int p, int n) {
reverse(data, 0, p - 1); // 前p个元素逆置
reverse(data, p, n - 1); // 后n-p个元素逆置
reverse(data, 0, n - 1); // 整个data进行1次逆置
}