链接: 旋转数组
要求我们转一次,就是把最后面的数移到最前面来,然后其他数字保持顺序往后移动一步。
常规思路: 就是用while循环,题目要求我们轮转n次,我们就将后n个数字分别移到最前面去。这种思路虽然行得通,但是仔细想,每次将前面的数字向后移,这个时间复杂度是不低的,所以我们这里不讲这种常规思路。
新思路: 题目要我们轮转数组,其实我们可以先将整个数组翻转顺序,然后再将前n - 1个数翻转顺序,最后将后numsSize - n个数翻转顺序(假设这里数组个数为numsSize个),其实就完成了数组轮转。
注:这里有一个关键的点,就是如果翻转n次,而n等于数组的长度numsSize的话,其实就是原数组不动,以此类推,所以我们可以对n进行一下处理。
而且这种思路的空间复杂度是O(1)的!
代码:
void partRotate(int* a, int left, int right)
{
//使用左右指针的方法
while(left < right)
{
int tmp = a[left];
a[left] = a[right];
a[right] = tmp;
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k){
k %= numsSize;
//若k模完长度为0,则无需轮转
if(k == 0)
return;
partRotate(nums, 0, numsSize - 1);//先翻转整个数组
partRotate(nums, 0, k - 1);//然后翻转前k - 1个
partRotate(nums, k, numsSize - 1);//最后翻转后numsSize - k个
}