Leetcode题目解析

用户11861691

发布于 2025-10-13 15:08:24

200

代码可运行

运行总次数：0

代码可运行

leetcode189 轮转数组（C语言）

https://leetcode.cn/problems/rotate-array/description/

题目解析

1. 思路一

我们可以先把数组最后一个数存起来，然后循环将前面的每个数向后移动一位，轮转k次，我们就将这个操作重复k次。

代码实现

void rotate(int* nums, int numsSize, int k) {
    while(k--)
    {
    int tmp=nums[numsSize-1];
    for(int i=numsSize-1;i>0;i--)
    {
        nums[i]=nums[i-1];
    }
    nums[0]=tmp;
    }
}

//时间复杂度O（N^2）
//空间复杂度O（1）

虽然改代码可以实现，但是我们可以根据我们之前学习的复杂度的知识计算一下该代码的时间和空间复杂度，时间复杂度为O（N^2），空间复杂度为O（1），显然，随着处理数据的增多，该代码的效率会十分低下，所以，我们需要优化一下思路。

2. 思路二

创建一个新的数组，用空间来换时间（画图往往可以帮助我们更好的理解分析题目）

代码实现

void rotate(int* nums, int numsSize, int k) {
    //创建新数组
    int tmp[numsSize];
    for(int i=0;i<numsSize;i++)
    {
        //当 i+k>numsSize 时，可以运用取余运算
        tmp[(i+k)%numsSize]=nums[i];
    }  
    //用for循环将tmp数组复制到nums数组中
    for(int i=0;i<numsSize;i++)
    {
        nums[i]=tmp[i];
    }
}

//时间复杂度O（N）
//空间复杂度O（N）

3. 思路三

通过上面的优化，我们将时间复杂度降了下来，但是空间复杂度升高了，是否有思路既可以省时间，又可以省空间

将数组整体逆置，再将前k个逆置，再将后n-k个逆置

代码实现

//创建一个逆置函数
void reverse(int*nums,int left,int right)
{
    while(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=k%numsSize;
    //整体逆置
    reverse(nums,0,numsSize-1);
    //前k个逆置
    reverse(nums,0,k-1);
    //后n-k个逆置
    reverse(nums,k,numsSize-1);
}

//时间复杂度O（N）
//空间复杂度O（1）

总结;算法题的思路是关键，而画图往往能够为我们打开思路。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-07-30，如有侵权请联系 cloudcommunity@tencent.com 删除

优化