复杂度--旋转数组方法一：使用额外数组方法二：数组反转：方法三、实现旋转：

74 阅读 0 评论 49 点赞

我是靠谱客的博主害羞季节，最近开发中收集的这篇文章主要介绍复杂度--旋转数组方法一：使用额外数组方法二：数组反转：方法三、实现旋转：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给你一个数组，将数组中的元素向右轮转 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]

方法一：使用额外数组

开辟一个全新的数组newarry用于储存数据，其中取余的思想最好画图更有利于理解。

时间复杂度：O(n),其中n为数组长度

空间复杂度：O(n)，开辟了一个大小为numsSize的数组空间

void rotate(int* nums, int numsSize, int k)
{
    int newarry[numsSize];
    for(int i=0;i<numsSize;i++)
    {
        newarry[(i+k)%numsSize]=nums[i];
    }
    for(int i=0;i<numsSize;i++)
    {
        nums[i]=newarry[i];
    }
}

或者下面这种写法更利于了解 ,其中k%=numsSize是考虑到k>numsSize的可能性

void rotate(int* nums, int numsSize, int k)
{
    k%=numsSize;
    int tmp[numsSize];
    int j=0;
    for(int i=numsSize-k;i<numsSize;i++)
    {
        tmp[j]=nums[i];
        j++;
    }
    for(int i=0;i<numsSize-k;i++)
    {
        tmp[j]=nums[i];
        j++;
    }
    for(int i=0;i<numsSize;i++)
    {
        nums[i]=tmp[i];
    }
}

方法二：数组反转：

首先将整个数组反转，其次将反转0--k个元素，再翻转k--numsSize的元素

时间复杂度：O(n)

空间复杂度：O(1)

void swap(int* a, int* b) //实现基础的元素换位
{
    int t = *a;
    *a = *b, *b = t;
}

void reverse(int* nums, int start, int end) 
{
    while (start < end) //实现数组范围内的元素换位
    {
        swap(&nums[start], &nums[end]);
        start += 1;
        end -= 1;
    }
}

void rotate(int* nums, int numsSize, int k)
{
    k %= numsSize;
    reverse(nums, 0, numsSize - 1);//先整体反转
    reverse(nums, 0, k - 1);//前翻转
    reverse(nums, k, numsSize - 1);//后翻转
}

其中reverse为数组翻转的实现，如果end-begin为偶数那么就所有数字都进行翻转，如果为奇数那么中间的数字不动，其余的数字翻转

方法三、实现旋转：

将数组前一位的值一次赋值给后一位，从而实现数组的旋转。总共执行k次

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