leetcode——旋转数组

思路一：
由该题的解题示例可以想到的最简单的一种思路
将数组最后一个元素取出，把剩余元素依次向右移动，最后将取出的最后一个元素放到数组的首位，要进行多少多少次数组旋转，就进行多少次操作

void rotate(int* nums, int numsSize, int k){
int temp=0;
int i=0;
int m=k%numsSize;
for(i=0;i<=m,i++)
{
    temp=nums[numsSize-1];
    for(int j=numsSize-2;j>0;--j)
    {
        nums[j+1]=nums[j];
    }
    nums[0]=temp;
}
}

此思路中时间复杂度为O(N*K),空间复杂度为O(1)
思路二：
对于时间有要求的题目，可以考虑以时间换取空间的思路，即开辟一块新的空间来降低时间复杂度
若是要求进行k次数组旋转操作，也就意味着将数组的后k位和数组的前numsSize-k位进行位置调换，因此另外建立一个数组，将后k位依次拷贝到新建的数组中，然后将原数组中剩下的元素依次拷贝到新数组中

void rotate(int* nums, int numsSize, int k){
 int* ret = (int*)malloc(sizeof(int)*numsSize);
 memset(ret, 0, sizeof(int)*numsSize);//开辟一个新数组
 int i = 0;
 int j = k%numsSize;//对旋转次数取余
 if (numsSize>1&&j!=0)//判断元素个数是否为一，若是一则不必处理
 {
  for (i = 0; i<j; i++)
  {
   ret[i] = nums[numsSize - j + i];//将nums数组中最后k个元素拷贝到ret数组中
  }
  for (i = 0; i<numsSize - j; i++)
  {
   ret[j + i] = nums[i];//把nums数组中前面的元素拷贝到ret数组中
  }
  for (i = 0; i<numsSize; i++)
  {
   nums[i] = ret[i];//将ret数组拷贝回原数组
  }
 }
}

注意点：
（1）当k=numsSize时，相当于原数组没有进行任何变化，当k>numsSize时，相当于进行了k%numsSize次数组旋转，所以一定要考虑到次数的边界问题
（2）要考虑到特殊情况：当数组的元素为一个或者numsSize=k时，输出的数组是和原数组完全相同的，因此在这里要做一个判断，若是满足条件，则不必再进行旋转操作
（3）在函数中若是开辟了新数组的一定要将新数组中的数据拷贝到原数组中
该死了时间复杂度为O（N），因为开辟了相同大小的数组，所以空间复杂度为O（N）
思路三：
若是进行k次数组旋转，将数组最后k个元素依次逆序，数组剩下的元素依次逆序，再把整个数组中的元素依次逆序

void reserve(int* nums,int left,int right)
{
    while(left<right)
    {
        int temp;
        temp=nums[left];
        nums[left]=nums[right];
        nums[right]=temp;
        ++left;
        --right;
    }//定义逆序函数
}
void rotate(int* nums, int numsSize, int k){
int j=k%numsSize;
reserve(nums,0,numsSize-j-1);//对数组前numsSize-k个元素进行逆序
reserve(nums,numsSize-j,numsSize-1);//对最后k个元素逆序
reserve(nums,0,numsSize-1);//整个数组逆序
}

该思路时间复杂度为O（N），空间复杂度为O（1）