分享力扣—189.轮转数组 的三种解法

---

题目名称

轮转数组力扣连接如下：

189. 轮转数组 - 力扣（LeetCode）

目录

题目名称

1.题目

2.题目分析

3.题目答案

---

---

推荐阅读顺序:

1.题目->2.题目分析->3.答案

---

1.题目

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/rotate-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

2.题目分析

这是一道编程题。

轮换数组可以通过创造中间变量的形式，也可以使用反转数组的解法。

---

3.题目答案

解1：

利用中间变量依次轮转：

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

由于时间复杂度较高不通过：

解2：

2.1  创建一个中间数组，以空间换取时间，这样做空间复杂度较高。

        时间复杂度 O(N)

#include<stdlib.h>

void rotate(int* nums, int numsSize, int k)
{
    int* arr = (int*)malloc(numsSize*4);
    int i = 0;
    for (i = 0; i < k; i++)
    {
         arr[i] = nums[numsSize - k + i];
    }
    for (i; i < numsSize; i++)
    {
        arr[i] = nums[i - k];
    }
    for (i = 0; i < numsSize; i++)
    {
        nums[i] = arr[i];
    }
}

2.2

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

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

 题解3：反转数组

void swap(int*nums,int begin,int end)
{
    int tmp=0;
    while(begin<end)
    {
        tmp=nums[begin];
        nums[begin]=nums[end];
        nums[end]=tmp;
        begin++;
        end--;
    }
}

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

---

你好，这里是媛仔，希望这篇解答能对你有所帮助，也欢迎大家和我多多交流，互相探讨，共同进步！^-^