开发者社区> 胡哥有话说> 正文

数组旋转,来来来,走个K步~

简介: 在前端算法面试中,数组是经常被问到的、使用到的。今天我们来看一道经典的前端基础面试题:【数组旋转K步】。
+关注继续查看

前言


在前端算法面试中,数组是经常被问到的、使用到的。今天我们来看一道经典的前端基础面试题:【数组旋转K步】。


首先来看下这个题目,假定存在数组 arr = [1, 2, 3, 4, 5, 6, 7],旋转 k = 3步,即数组末尾的元素依次进行挪动到数组的前面,即结果为 [5, 6, 7, 1, 2, 3, 4]


题目其实不太难,我们借助这个题目来了解一下算法复杂度(时间复杂度、空间复杂度)以及数组中一些原生方法产生不同复杂度的问题


实现-方案1


思路很简单,每旋转一步,将数组末尾的最后一个元素取出,然后再插入到数组的最前面。


注意边界值问题考虑!!


/**
* @method rotate
* @description 数组渲染K步
* @param arr number[]
* @param k number
*/
function rotate (arr: number[], k: number): number[] {
  const len = arr.length;
  
  // 此处考虑边界值问题
  
  // 数组为空
  if (len === 0) {
    return arr;
  }
  
  // K步 - K的取值
  // 如果是负值直接给处理为正数,取绝对值
  // 如果是 k > len 即大于数组长度时,取余数
  // 如 arr 的 len === 5,设置 k === 9,其实相当于将数组旋转一圈之后,再走了 k % len === 4 步
  const step = Math.abs(k % len);
  
  for (let i = 0; i < step; i++) {
    // 每次取出最后一个元素
    const lastEle = arr.pop();
    
    // 将取出的元素,放入到数组的最前面
    // 因为pop方法可能会抛出一个undefined值,实际我们已经约束了,不会出现这个情况,但是ts会进行检测,所以这个位置添加了@ts-ignore
    // @ts-ignore
    arr.unshift(lastEle);
  }
  
  return arr;
}


是骡子是🐴拉出来遛遛~~~


const arr = [1, 2, 3, 4, 5, 6, 7];
console.log(rotate(arr, 3)) // [5, 6, 7, 1, 2, 3, 4]


通过该方案结果是有了,那这个是一个非常优秀的方案吗?我们来分析下该实现的时间复杂度和空间复杂度。


空间复杂度:


在该函数中没有新产生一个空间对象,还是数组arr本身,所以空间复杂度是O(n)O(n)O(n),是可接受的。


时间复杂度:


在该函数中有一层for循环,此处时间复杂度是O(n)O(n)O(n);


同时在函数的内部中涉及到了数组元素的移动 unshift。大家都知道数组在内存中是以连续内存的方式进行存储的,以数组arr = [1, 2, 3, 4, 5, 6, 7]为例,如果想将元素7移动到数组的最前面,需要依次将数组元素6、5、4、3、2、1依次向后移动,然后将7插入,所以unshift方法的时间复杂度是O(n)O(n)O(n)。pop方法只是将数组最后一个元素弹出,基本可以不考虑时间损耗。


整体的时间复杂度为O(n)∗O(n)O(n) * O(n)O(n)∗O(n),即O(n2)O(n^2)O(n2),是不太理想的。


实现-方案2


我们一起来瞅瞅有没有一种更优的方式呢。


换个角度考虑下,从最终的结果来看,旋转k步,即将数组最后的k个元素取出,与剩余的其他元素进行拼接,返回最终结果,从代码上表示为:[5, 6, 7].concat([1, 2, 3, 4])


各位小伙伴,解题思路已经转变到如何从数组arr中截取出[5, 6, 7][1, 2, 3, 4],很简单,数组的slice方法解决问题。


上代码


/**
* @method rotate2
* @description 数组渲染K步
* @param arr number[]
* @param k number
*/
function rotate2 (arr: number[], k: number) {
  // 获取数组长度
  const len = arr.length;
  // 同样的边界值判断
  if (len === 0) {
    return arr;
  }
  // 取余、取绝对值
  // 逻辑同上
  const step = Math.abs(k % len);
  // slice调用时传递负数,为取出最后的step个元素
  const p1 = arr.slice(-step);
  // 取出前面的0 至 len-step个元素
  const p2 = arr.slice(0, len - step);
  
  // 拼接新数组返回
  return p1.concat(p2);
}


我们来看下这个实现的时间复杂度和空间复杂度。


空间复杂度:


虽然该算法实现中,返回了一个新数组,看起来似乎比方案1的实现多声明了一个变化,但从量级上来说,还是一个O(n)O(n)O(n)的复杂度,是可接受的。


时间复杂度:


在该算法中没有循环,只是单纯的调用了slice方法,截取了数组元素,同时也没有影响数组arr本身,所以可以将该算法视为常量级的时间复杂度O(1)O(1)O(1)。


有可能会有小伙伴对slice操作视为O(1)O(1)O(1)时间复杂度有疑问。在JS中,数组在内存中是连续存储的,也就是说我们能够根据索引,快速定位到元素,进而执行。这个操作是非常快速的,视为常量级O(1)O(1)O(1)


方案比较:


我们在谈论时间复杂度和空间复杂度时讨论的是一个量级问题,不是一个绝对值问题。也就是说随着数组arr的长度越大,旋转的k值越大,时间复杂度为O(1)O(1)O(1)方案2的性能要远远的比时间复杂度为O(n2)O(n^2)O(n2)的方案1优秀的多。


我们可以使用console.time()、console.timeEnd(),来进行性能的测试。


我们依次使用一个10W、100W长度的数组,旋转100步、1000步,来对比二者的性能。


定义一个可以生成指定长度数组的方法:


/**
 * @method makeArr
 * @description 根据传入的长度len生成指定长度的数组
 * @param len number 指定的数组长度
 */
function makeArr(len: number): number[] {
  const arr: number[] = [];
  for (let i = 0; i < len; i++) {
    arr.push(i);
  }
  return arr;
}


10W条数据比较:


// 指定长度10W
const len = 10 * 10000;
// 第一个方案
const arr = makeArr(len);
console.time("rotate1");
const res = rotate(arr, 100);
console.timeEnd("rotate1");
// 第二个方案
const arr2 = makeArr(len);
console.time("rotate2");
const res2 = rotate2(arr2, 100);
console.timeEnd("rotate2");


结果上图:


image


100W条数据比较:


// 指定长度10W
const len = 100 * 10000;
// 第一个方案
const arr = makeArr(len);
console.time("rotate1");
const res = rotate(arr, 1000);
console.timeEnd("rotate1");
// 第二个方案
const arr2 = makeArr(len);
console.time("rotate2");
const res2 = rotate2(arr2, 1000);
console.timeEnd("rotate2");


结果上图:


image


注:不同配置的电脑在上述测试中,结果数值是存在差异性的。


效果还是非常明显的啦,二者对比,方案2要远胜于方案1


小课堂


在数组中方法的操作中,注意数组的方法 unshiftshiftsplice涉及数组元素的移动,是非常损耗性能的。


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
14852 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
15291 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
18581 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
36341 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
19980 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
27727 0
70
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载