Leetcode每日一题——“轮转数组”

各位CSDN的uu们你们好呀，今天，小雅兰的内容是轮转数组，下面，让我们进入轮转数组的世界吧

小雅兰之前其实就已经写过了字符串旋转的问题了：

C语言刷题（7）（字符串旋转问题）——“C”_认真学习的小雅兰.的博客-CSDN博客 

示例 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]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

方法一：

暴力求解法，旋转k次

 但是，这样求解时间复杂度为O（N^2），空间复杂度为O（1）

 不符合题目要求

 那么此方法，小雅兰就不用代码来实现啦

方法二：

三步翻转法

原数组：1 2 3 4 5 6 7 

前n-k个逆置：4 3 2 1 5 6 7

后k个逆置：4 3 2 1 7 6 5

整体逆置：5 6 7 1 2 3 4

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

满足题目要求

void reverse(int* arr,int left,int right)
{while(left<right){int tmp=arr[left];arr[left]=arr[right];arr[right]=tmp;left++;right--;}
}
void rotate(int* nums, int numsSize, int k)
{if(k>numsSize){k%=numsSize;}reverse(nums,0,numsSize-1-k);reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-1);
}

方法三：

空间换时间的方法

 使用额外的数组来将每个元素放至正确的位置

 不能用strcpy，strcpy是专门处理字符串的函数

void rotate(int* nums, int numsSize, int k){if(k>numsSize){k%=numsSize;}int*tmp=(int*)malloc(sizeof(int)*numsSize);memcpy(tmp+k,nums,sizeof(int)*(numsSize-k));memcpy(tmp,nums+numsSize-k,sizeof(int)*(k));memcpy(nums,tmp,sizeof(int)*(numsSize));free(tmp);tmp=NULL;
}

好啦，小雅兰今天的轮转数组就到这里啦，还要继续加油刷题噢！！！