leetcode每日一练：旋转数组

链接: 旋转数组

要求我们转一次，就是把最后面的数移到最前面来，然后其他数字保持顺序往后移动一步。

常规思路： 就是用while循环，题目要求我们轮转n次，我们就将后n个数字分别移到最前面去。这种思路虽然行得通，但是仔细想，每次将前面的数字向后移，这个时间复杂度是不低的，所以我们这里不讲这种常规思路。

新思路： 题目要我们轮转数组，其实我们可以先将整个数组翻转顺序，然后再将前n - 1个数翻转顺序，最后将后numsSize - n个数翻转顺序（假设这里数组个数为numsSize个），其实就完成了数组轮转。

注：这里有一个关键的点，就是如果翻转n次，而n等于数组的长度numsSize的话，其实就是原数组不动，以此类推，所以我们可以对n进行一下处理。

而且这种思路的空间复杂度是O(1)的！

代码：

代码语言：javascript复制

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个
}

leetcode 数组

0 人点赞