空间换时间：数据结构中时间复杂度于空间复杂度的“转换”

引言：���些数据结构题目，对一些新上手的小白很不友好，这里推荐一种“笨方法” ：空间换时间

（）

思路：利用额外开辟的空间，增加空间复杂度，去减少传统暴力求解的时间开销

举例：

（）

189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3输出: [5,6,7,1,2,3,4]解释:向右轮转 1 步: [7,1,2,3,4,5,6]向右轮转 2 步: [6,7,1,2,3,4,5]向右轮转 3 步: [5,6,7,1,2,3,4]

观察解释，可知题目中给的思路是暴力求解法

一、空间换时间法：将需要逆序的前半段传给另一个空间的后半段，后半段传给前半段

void rotate(int* nums, int numsSize, int k) {

    k %= numsSize;

    int* p = (int*)malloc(sizeof(int) * numsSize);           //额外开辟空间

    memcpy(p + k, nums, (numsSize - k) * sizeof(int));      //dest  src  num（字节数）

    memcpy(p, nums + numsSize - k, k * sizeof(int));

    memcpy(nums, p ,sizeof(int) * numsSize);    

                     // nums = p;    //不允许！   将p释放之后，nums指向的内容变成随机值

    free(p);

    p = NULL;

   

}

//此时的空间复杂度为O（N） //额外用malloc开辟了4 * numsSize个字节的空间

二、最优解：三段逆置法

思路：（题目已经提示你，轮转数组！！！）

1.先反转整个数组

2.再反转数组的 1~K 项

3.再反转 K~numsSize 项

4.得到结果

void reverse(int* p, int left, int right)      //为了第三次旋转，需要自己传左右位置

{

    //对两端进行操作的时候，一般定义left 和 right 作为下标

    while(left