题目

假设现在有一个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;
}