旋转数组

来源：力扣（LeetCode）
链接： 189.旋转数组

文章目录

旋转数组

一、题目

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

二、解题思路分析

1. 暴力循环求解

按照它的思路，旋转k次，把旋转k次分成k份，每份都是旋转1次

先保存最后一个数字，往前的每一个数字都向后挪一位
在这里插入图片描述

但力扣好像会溢出

void rotate(int* nums, int numsSize, int k){
    int i = 0;
    int j = 0;
    k = k % numsSize;

    for(i = 0; i < k; i++)//交换k次
    {
        int ret = *(nums + numsSize -1);

        for(j = 0; j < numsSize - 1; j++)//交换一次
        {
            nums[numsSize - 1 - j] = nums[numsSize - 2 - j];
        }
        nums[0] = ret;

    }

}

如果用内存拷贝代码会简单一点

void rotate(int* nums, int numsSize, int k){
    int i = 0;
    for(i = 0; i < k; i++)
    {
        int ret = nums[numsSize - 1];
        memmove(nums + 1, nums, (numsSize - 1) * sizeof(int));
        nums[0] = ret;

    }
}

时间复杂度：O(kn)

空间复杂度：O(1)

2. 额外数组，利用空间换时间

可以使用额外的数组来将每个元素放至正确的位置

创建数组的时候，虽然在oj中可以

int newArr[numsSize];

????但在编译器中是不允许的

在这里插入图片描述

????会出现错误

这样我们先用malloc开辟内存空间

void rotate(int* nums, int numsSize, int k){
    int* tmp = (int*)malloc(sizeof(int) * numsSize);
    if(tmp == NULL)
    {
        exit(-1);
    }    
}

将每个数的正确位置放在新的数组里，最后复制到原数组中，最后别忘记释放内存空间

在这里插入图片描述

void rotate(int* nums, int numsSize, int k){
    int* tmp = (int*)malloc(sizeof(int) * numsSize);
    if(tmp == NULL)
    {
        exit(-1);
    }

    int i = 0;
    for(i = 0; i < numsSize; i++)
    {
        tmp[(i + k) % numsSize] = nums[i];

    }
    for (int i = 0; i < numsSize; ++i) 
    {
        nums[i] = tmp[i];
    }
    free(tmp);
    tmp =NULL;
    
}

时间复杂度：O(2n)

空间复杂度：O(n)

3. 数组翻转

类似于字符串翻转，在字符串中我们遇到，字符串倒序/字符串翻转/字符串左旋

abcdef -> cdefab

我们先将 ab 逆序 -> ba

再将 cdef 逆序 -> fedc

最后将 ba fedc 逆序

得到 cdefab

数组可以用同样的方式

void reverse(int* nums, int numsSize)
{
    int i = 0;
    int ret = 0;
    for(i = 0; i < numsSize/2; i++)
    {
        ret = nums[i];
        nums[i] = nums[numsSize - 1 - i];
        nums[numsSize - 1 - i] = ret;
    }

}

void rotate(int* nums, int numsSize, int k){
    k = k % numsSize;
    if(k > 0)
    {
        reverse(nums, numsSize - k);
        reverse(nums + numsSize - k, k);
        reverse(nums, numsSize);
    }

    
}