💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤

📃个人主页 ：阿然成长日记 👈点击可跳转

📆 个人专栏： 🔹数据结构与算法🔹C语言进阶

🚩 不能则学，不知则问，耻于问人，决无长进

🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍

💬前言：

🌸 hello大家好✨又见面了 。

本篇算法中关于数组问题，很适合刚开始学习数据结构与算法的小伙伴学习。小编也是刚刚开始，希望一起学习，多多交流，共同进步！

📋题目要求

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

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3

输出: [5,6,7,1,2,3,4]

解释:

1.向右轮转 1 步: [7,1,2,3,4,5,6]

2.向右轮转 2 步: [6,7,1,2,3,4,5]

3.向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2

输出：[3,99,-1,-100]

解释:

1.向右轮转 1 步: [99,-1,-100,3]

2.向右轮转 2 步: [3,99,-1,-100]

📑 解题思路

🕜1.暴力求解

思路：右旋K次。

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

复杂度分析：

时间复杂度 O(N^2),

空间复杂度 O(1),

🔸暴力求解思路十分简单，但是非常耗费时间，这里就已经运行超出时间限制啦。

🕜方法二

在K的位置截断，将K前数组与K后的数组交换位置 。

1️⃣ 这里我们的办法是先将nums数组后k个数放到tmp新数组中

2️⃣ 再将nums的前n-k个数放入tmp中

3️⃣最后，再将已经排好的数组放回nums中，便于此题函数的返回是nums，tmp只是我们临时建立的数组。

void rotate(int* nums, int numsSize, int k)
{
  int* tmp = (int*)malloc(sizeof(int) * numsSize);
  int n = numsSize;
  k %= n;
  memcpy(tmp, nums + n - k, sizeof(int) * k);
  memcpy(tmp+k, nums , sizeof(int) * (n - k));
  memcpy(nums,tmp, sizeof(int) * (n));
}

根据分析：

时间复杂度：O（N）；

空间复杂度：O（N）；

🔸这种方法其实就是在用空间 换 时间。

这里我们使用了库函数中的memcmp函数，具体函数使用讲解

友友们，可以点击这里👉memcmp函数的详解

方法三：

逆置法:

思路

1️⃣ 以n+k为准，分为两部分

2️⃣ 各数组进行逆置

3️⃣ 最后，在整体数组逆置

代码实现

void reverse(int* a, int left, int right)
{
  while (left < right)
  {
    int tmp = a[left];
    a[left] = a[right];
    a[right] = a[tmp];
    left++;
    right--;
  }
}
void rotate(int* nums, int numsSize, int k)
{
  k%= numsSize;
  reverse(nums, 0, numsSize - k - 1);
  reverse(nums, numsSize - k, numsSize - 1);
  reverse(nums, 0, numsSize - 1);
}

可见，这种方法的效率十分的快，就是很难想到。

时间复杂度：O(N)

空间复杂度：O(N)

总结

关于数组的算法题，一般不会太难，学会找到最高效的那种方法，并掌握它是最关键的。

各位看官老爷，咱下回再见！

别忘了点赞关注加评论哟

💙 💜 ❤️ 💚 💔 💓 💗 💕 💞 💘 💖 ✨ ⭐️ 🌟