Leetcode-轮转数组
题目描述
思路1
时间复杂度O(n^2)
循环K次将数组所有元素向后移动⼀位（代码不通过
）
void rotate(int* nums, int numsSize, int k)
{
while(k--)
{
int end = nums[numsSize-1];
for(int i = numsSize - 1;i > 0 ;i--)
{
nums[i] = nums[i-1];
}
nums[0] = end;
}
}
思路2：
空间复杂度 O(n)
申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中
void rotate(int* nums, int numsSize, int k)
{
int newArr[numsSize];
for (int i = 0; i < numsSize; ++i)
{
newArr[(i + k) % numsSize] = nums[i];
}
for (int i = 0; i < numsSize; ++i)
{
nums[i] = newArr[i];
}
}
思路3：
空间复杂度 O(1)
•
前n-k个逆置：
4 3 2 1
5 6 7
•
后k个逆置 ： 4 3 2 1
7 6 5
•
整体逆置 ：
5 6 7 1 2 3 4
void reverse(int* nums, int left, int right)
{
while(left<=right)
{
//left和right的数据进行交换
int tmp=nums[left];
nums[left]=nums[right];
nums[right]=tmp;
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k)
{
k=k%numsSize;
//前n-k个数据逆置
reverse(nums,0,numsSize-k-1);
//后k个数据逆置
reverse(nums,numsSize-k,numsSize-1);
//整体逆置
reverse(nums,0,numsSize-1);
}