【LeetCode】189. 轮转数组-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode】189. 轮转数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接：https://leetcode.cn/problems/rotate-array/

📕题目要求：

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？

【LeetCode】189. 轮转数组

🧠解题思路

方案一：暴力求解

旋转k次，一次旋转一个。每次将最右边的数字保存一下，然后依次将剩余的元素进行右移，最后将保存的数字添加到最左侧即可。

时间复杂度最坏为：O(N^2)

空间复杂度为：O(1)

此方法效率过低，这里就不进行赘述。

方案二：三段逆置

先将前n-k个元素进行逆置，再将后k个元素进行逆置，最后将数组整体逆置。

【LeetCode】189. 轮转数组

时间复杂度为：O(N)

空间复杂度为：O(1)

方案三：空间换时间

另外开辟一段空间tmp，将nums数组中后k个元素先拷贝到tmp，再将num数组中前n-k个元素拷贝到tmp中。最后将tmp中的元素拷贝覆盖到nums中，销毁tmp，返回nums。

【LeetCode】189. 轮转数组

🍭代码示例

方案二代码示例如下：

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)
{
    if(k>=numsSize)
    {
        k%=numsSize;
    }
    reverse(nums,0,numsSize-k-1);
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-1);
    return nums;
}

方案三代码示例如下：

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

在进入数据结构部分，我还是建议大家可以试试画图理解比较有用，我今后也会可以去训练这部分的能力。

这就是我对本题的理解，如果大家有更优的解，欢迎交流，一起进步！

【LeetCode】189. 轮转数组文章来源地址https://www.toymoban.com/news/detail-426996.html