189. 轮转数组

轮转数组

题目描述：

➡️挑战链接⬅️
分析：
题目描述很简单，草草几句话就盖过了，当然输入实例也有对此的描述；
方法一：
首先，对于这道题来说我们最容易想到的就是暴力法；
我们将元素一个一个的旋转，总共旋转k次就行了：
我们每次在旋转之前都先将最后一个位置的元素保存一下，然后依次将[0,numsSize-2]区间的元素往后挪一个位置，最后下标为0的位置会被空出来，我们最后再把刚才保留的值放进去就完成了依次反转，随后重复上面步骤k次就可以完成题目要求了；
画图演示：

当然在这里我们要注意一个小细节，就是根据题目给出的k的范围，我们可以看出，k的范围是有可能超出数组长度的，这也就意味着我们会进行许多重复的操作，为了节省时间，我们应该对其和数组长度进行取模；

时间复杂度：O（N^2）
空间复杂度：O（1）

代码实现：

void rotate(int* nums, int numsSize, int k){
       k%=numsSize;
       for(int i=0;i<k;i++)
       {
           int tmp=nums[numsSize-1];
           for(int end=numsSize-2;end>=0;end--)
           {
               nums[end+1]=nums[end];
           }
           nums[0]=tmp;
       }
}
1
2
3
4
5
6
7
8
9
10
11
12

直接超时；说明暴力法还是不行；
我们接着来看
方法二：借用临时数组
既然暴力法是一个一个的反转，我们能不能一次性就完成反转？
当然可以，我们可以创建一个临时数组，将被反转k个值先全部保留在临时数组里卖，然后呢，将元素组剩下值在依次往后挪k个位置，最后再将临时数组里面的元素全部拷贝会元素组的前k个位置，这样，我们就完成了对数组的轮转；
画图演示：

代码实现：

void rotate(int* nums, int numsSize, int k){
              k%=numsSize;
              if(!k)//处理下k等于0的情况
              return;
              int tmp[k];
              int n=0;
              //1、将[numsSize-k,numsSize-1]元素拷贝进tmp数组;
              for(int i=numsSize-k;i<numsSize;i++)
              {
                  tmp[n++]=nums[i];
              }
              //2、将[0,numsSize-k-1]往后挪k个单位
              for(int end=numsSize-k-1;end>=0;end--)
              {
                  nums[end+k]=nums[end];
              }
              //3、将tmp里的元素拷贝回原素组
              for(int j=0;j<n;j++)
              {
                  nums[j]=tmp[j];
              }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度：O（N）
空间复杂度：O（1）

那么还有没有更优的解法呢？
当然有！
方法三：三步翻转法
只能说发明这个方法的人，真tmNB，到底是怎样的脑袋才能想出这么棒的方法；
该方法的主要思想是：只需将数组反转3次就可以完成目标了；
所以叫三步反转；
当然这三步反转，都是针对特定的区间进行的；
画图演示：

时间复杂度：O（N）
空间复杂度：O（1）

代码实现：

void reverse_num(int *nums,int left,int right)
{ 
    while(left<right)
    {
        int tmp=nums[left];
        nums[left]=nums[right];
        nums[right]=tmp;
        left++;
        right--;
    }
}
//1、三步翻转法
//时间复杂度：O（N）
//空间复杂度：O（1）
void rotate(int* nums, int numsSize, int k){
          k%=numsSize;
          reverse_num(nums,0,numsSize-1);
          reverse_num(nums,0,k-1);
          reverse_num(nums,k,numsSize-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20