题目
假设现在有一个array[m+n]数组，前m个为a线性表，后n个为b线性表，在空间复杂度为o(1)的情况下，完成2个数组位置的交换。
分析
题目看起来不难，我一开始的思路是malloc一块相同大小的数组，再将2个表的顺序颠倒即可实现，但是空间复杂度为o(1)的情况下(也就是所使用的空间不与array[]数组的长度产生关系)，想要实现，确实需要巧妙的方法
解法思路
Step 1 初始状态
0 1 2 3 4
+--------------+--------------+--------------+--------------+--------------+
| a | b | c | d | e |
+--------------+--------------+--------------+--------------+--------------+
|<- a表 ->|<- b表 ->|
Step2 让a表逆序
0 1 2 3 4
+--------------+--------------+--------------+--------------+--------------+
| c | b | a | d | e |
+--------------+--------------+--------------+--------------+--------------+
|<- a表 ->|<- b表 ->|
Step3 让b表逆序
0 1 2 3 4
+--------------+--------------+--------------+--------------+--------------+
| c | b | a | e | d |
+--------------+--------------+--------------+--------------+--------------+
|<- a表 ->|<- b表 ->|
Step4 让整个表逆序
0 1 2 3 4
+--------------+--------------+--------------+--------------+--------------+
| d | e | a | b | c |
+--------------+--------------+--------------+--------------+--------------+
|<- b表 ->|<- a表 ->|
实现代码
编译环境为windows,mingw64，vs系列可能会出现像for循环变量书写错误，变量没有声明在最前等报错，请适当修改，谢谢。也希望有更多写法的朋友在评论里给出代码一起讨论
#include <stdio.h>
#include <malloc.h>
/*
* 用于打印数组，可忽略
*/
void print_array(int a[], int len) {
for (int i = 0; i < len; i++) {
printf("%4d", a[i]);
if (i != 0 && i % 10 + 1 == 0 )printf("\n");
}
printf("\n ");
}
/*
* ！核心代码 执行数组的逆序操作
*/
int reverse(int start, int end, int a[]) { //需要数组的 起点下标
//和 结束下标 （注意是下标！！)
int mid = (end - start + 1) / 2;
int temp = 0;
for (int i = 0; i < mid; i++) {
temp = a[start + i];
a[start + i] = a[end - i];
a[end - i] = temp;
}
}
/*
* 核心代码 整个操作的交换
*/
int totalReverse(int m, int n, int a[]) {
reverse(0, m - 1, a); //先逆序a线性表，也就是逆序从 0 号位 到 m-1 号位
reverse(m, m + n - 1, a); //再逆序b线性表，从m 号位到 m+n-1 号位
reverse(0, m + n - 1, a); //整个数组再逆序一遍，即可完成 两个线性表位置交换的操作
}
int main() {
int len = 50; //数组的长度为50
int *a = malloc(sizeof(int) * len);
for (int i = 0; i < len; i++) {
a[i] = i;
}
totalReverse(20,30,a);
print_array(a, len);
return 0;
}
