力扣189 - 轮转数组【空间换时间、三步翻转法】

简介: 对应力扣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]
  • 本题的题目思路很简单,就是给你一个数组,然后将这个数组中后k个数字一一翻转到前面来,最后得到的就是向右轮转后的数组
  • 本题比上一题复杂一些,有一些边界值需要考虑,【因此建议大家画图】

三、方法1:直接翻转移动【超时】

  • 外层的while循环执行的是k的翻转次数,内层的for循环实现的是逐步的移位操作,因此时间复杂度为O(k * numsSize),若是这个k == numsSize,那么时间复杂度将会到达==O(N^2^)==,在力扣上O(N^2^)的时间复杂度是很容易超时的,所以不建议大家使用此方法
//超时
while(k--)
{
    int ret = nums[numsSize - 1];
    for(int i = numsSize - 1;i > 0; i--)
        nums[i] = nums[i - 1];
    nums[0] = ret;
}

三、方法2:空间换时间【C语言】

1、思路分析

首先第一个思路是使用空间换时间的思想,也就是将每次移动的数字放入另一个数组,最后拷贝回来
  • 讲一下整体的思路,首先你需要一个数组,去存放临时放置的数字
  • 然后要将后k个数字移动到前面
  • 其次将n - k个数字移动到后面
  • 最后将移动完的数组再拷贝绘原数组

2、整体代码展示

我们来看一下代码
void rotate(int* nums, int numsSize, int k){
    int n = numsSize;
    int tmp[n];      //变长数组【C99】

    //1.首先对k做一个取模操作,防止数组访问越界
    k %= n;
    //2.将后k个数字移动到前面
    int j = 0;
    for(int i = n - k;i < n; ++i)
       tmp[j++] = nums[i]; 

    //3.n - k个数字移动到后面
    for(int i = 0;i < n - k; ++i)
        tmp[j++] = nums[i];

    //4.将移动完的数组再拷贝绘原数组
    for(int z = 0;z < n;++z)
        nums[z] = tmp[z];
}

力扣提交结果
很明显,内存消耗比较多,因为需要维护一个临时数组

在这里插入图片描述

3、代码详解

然后我们对这段代码来详细讲解一下
  • 首先我们需要一个临时放置的数组,因此开辟一个变长数组,这个在力扣上应该是可以过的,C99新出的特性,C89不支持,可能在VS这样的编译器上会报错
  • 然后我们先跳过取余的这一段逻辑,看下面
  • 首先就是要将后k个数字移动到前面,我们通过图示来看一下
在这里插入图片描述
  • 可以看到,我们需要移动的是5~7这三个数组,此时你应该通过题目已经给出的n和k去判断边界值,5所在的位置是下标4,7所在的位置是n - 1,7后面就是n,这个时候需要你去联想一下通过下面的几个案例算一下,其实就可以发现后面需要翻转的初始位置应该是【n - k】
  • 然后对于循环的边界我们最好是写成左闭右开的形式,所以【< n】即可
//1.首先对k做一个取模操作,防止数组访问越界
k %= n;
//2.将后k个数字移动到前面
int j = 0;
for(int i = n - k;i < n; ++i)
   tmp[j++] = nums[i]; 

  • 然后第二步,我们要将前n - k个数字移动到后面
  • 这个时候就体现出画图的重要性的,从下图可以看出,当后k个数字移动到赋值到临时数组中时,这个递增变量j也就刚好移动到了临时数组此时需要开始放置的起始位置,因此我们只需要考虑拷贝那一段便可
在这里插入图片描述
  • 很明显可以知晓,前n - k个数字从0开始,边界值就是n - k - 1,使用左闭右开的形式来写【< n - k】即可
//3.n - k个数字移动到后面
for(int i = 0;i < n - k; ++i)
    tmp[j++] = nums[i];
  • 当临时数组中已经存放好了需要翻转的数字后,我们将临时数组中的数字全部拷贝会原数组即可
//4.将移动完的数组再拷贝绘原数组
for(int z = 0;z < n;++z)
    nums[z] = tmp[z];

但是你会发现,就这样提交会出现执行出错,会出现一个溢出的情况,这是为什么呢?这个时候就需要使用到我开头跳过的那句代码
//1.首先对k做一个取模操作,防止数组访问越界
k %= n;
  • 假设k = 3,n = 7,那就是我们例子中的翻转
  • 假设k = 7,n = 7,形成的是一个整体翻转
  • 假设k = 8,n = 7,此时需要翻转的数字个数大于题目给出的数字个数,其实翻转8次就是翻转1次,对应了我们题目中的【轮】这个字眼,也就是一轮满了,需要重新开启第二轮,那这个时候就需要使用到取余【%】这么一个操作

在这里插入图片描述

在这里插入图片描述

  • 此时你再去提交,就发现没什么问题<(^-^)>

四、方法3:三步翻转法【C++】

1、思路分析

接下来再介绍一种比较巧妙的办法,就是【三步翻转法】
  • 整体的思路就是现将前n - k个数字做一个翻转,然后将后k字数字做一个反转,最后将整个数组做一个翻转,思路很简单,但是不容易想到

2、整体代码展示

先看一下整体的代码
class Solution {
private:
    void trans(vector<int>&nums, int begin, int end)
    {
        for(int i = begin, j = end; i <= j; ++i, --j)
            swap(nums[i],nums[j]);
    }
public:
    void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    k %= n;
    //1.首先将前n-k个数字翻转
    trans(nums, 0, n - k - 1);

    //2.然后将后k个数字翻转
    trans(nums, n - k, n - 1);
        
    //3.最后将整体做一个翻转
    trans(nums, 0, n - 1);
    }
};

力扣提交结果
可以看出,整体的效率较新开辟一个临时数组来的高效一些

在这里插入图片描述

3、代码详解

来分析一下代码
  • 首先需要将翻转的逻辑封装成一个函数,使用双指针的思路,做一个前后翻转即可,这个我们之前做字符串翻转的题目里也有讲到过
void trans(vector<int>&nums, int begin, int end)
{
    for(int i = begin, j = end; i <= j; ++i, --j)
        swap(nums[i],nums[j]);
}
  • 然后在主接口也是一样,需要先对这个k进行一个取余的操作,保证数组不会访问越界
  • 接下去就是三次翻转,我写的非常清晰,只需要传入边界值给到封装好的函数即可
  • 对于边界值的判断,非常重要,这一点我不细讲。希望你可以自己去试着画画图,对题目的理解也是有很好的帮助,下面给到流程图参考一下
在这里插入图片描述

五、总结与提炼

  • 本文我们主要是讲解了一道力扣题,叫做【轮转数组】,面对题目给出的数组和k,需要将后k个数字翻转到前面特别要注意的是这个k可能会大于数组的长度,所以需要进行一个取余的操作
  • 在本文中,主要是给出了三种解法【直接翻转移动】、【空间换时间】、【三步翻转法】,对于第一种方法不建议,复杂度较高,易超时,第二种空间换时间的思路大家应该都可以想到,但是效率不高,最后一种三步翻转法比较巧妙,整体的效率也比较高一些,重点掌握
以上就是本文的所有内容,如有问题请于评论区留言或者私信我,感谢您对本文的观看:hibiscus:
相关文章
|
5月前
|
存储 算法 数据可视化
力扣155题最全解法:如何实现支持常数时间获取最小值的最小栈(附详细图解和复杂度分析)
力扣155题最全解法:如何实现支持常数时间获取最小值的最小栈(附详细图解和复杂度分析)
|
6月前
leetcode代码记录(使用最小花费爬楼梯
leetcode代码记录(使用最小花费爬楼梯
34 0
|
11月前
|
算法 测试技术 C#
C++前缀和算法的应用:得到连续 K 个 1 的最少相邻交换次数 原理源码测试用例
C++前缀和算法的应用:得到连续 K 个 1 的最少相邻交换次数 原理源码测试用例
|
6月前
|
算法 测试技术 索引
【二分查找】LeetCode2141: 同时运行 N 台电脑的最长时间
【二分查找】LeetCode2141: 同时运行 N 台电脑的最长时间
|
11月前
|
算法 测试技术 C#
C++前缀和算法的应用:装包裹的最小浪费空间 原理源码测试用例
C++前缀和算法的应用:装包裹的最小浪费空间 原理源码测试用例
【Leetcode -面试题17.04.消失的数字 -189.轮转数组】
【Leetcode -面试题17.04.消失的数字 -189.轮转数组】
38 0
算法训练Day38|● 509. 斐波那契数 ● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯
算法训练Day38|● 509. 斐波那契数 ● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯
【每日一道LeetCode】——面试题 17.04. 消失的数字、189. 轮转数组
【每日一道LeetCode】——面试题 17.04. 消失的数字、189. 轮转数组
【每日一道LeetCode】——面试题 17.04. 消失的数字、189. 轮转数组
|
开发者 索引
力扣刷题记录——482. 密钥格式化、485.最大连续1的个数、492. 构造矩形
力扣刷题记录——482. 密钥格式化、485.最大连续1的个数、492. 构造矩形
128 0
力扣刷题记录——482. 密钥格式化、485.最大连续1的个数、492. 构造矩形
|
存储 机器学习/深度学习
复制带随机指针的链表(中等难度)
复制带随机指针的链表(中等难度)
69 0
复制带随机指针的链表(中等难度)