JavaScript算法题之如何将一个数组旋转k步

目录
  • 一、题目描述:
  • 二、思路分析:
    • 两种思路:
      • 思路1:把末尾的元素挨个pop,然后unshift到数组后面
      • TS代码
      • 运行结果
      • 思路2:把数组拆分,最后concat拼接到一起
      • TS代码
      • 运行结果
  • 三、总结:
  • 四、划重点

一、题目描述:

将一个数组旋转k步

  • 输入一个数组[1,2,3,4,5,6,7,8]
  • 当k=3时,即旋转3步
  • 输出[6,7,8,1,2,3,4,5]

二、思路分析:

两种思路:

  • 把末尾的元素挨个pop,然后unshift到数组后面
  • 把数组拆分,最后concat拼接到一起

思路1:把末尾的元素挨个pop,然后unshift到数组后面

  • JavaScript Array pop() 方法

删除数组的最后一个元素:

var fruits = ["Banana", "Orange", "Apple", "Mango"];
fruits.pop();
  • JavaScript Array unshift() 方法

将新项目添加到数组的开头:

var fruits = ["Banana", "Orange", "Apple", "Mango"];
fruits.unshift("Lemon","Pineapple");

TS代码

function rotate1(arr:number[],k:number):number[]{
    const length = arr.length
    if(!k||length===0)return arr
    const step = Math.abs(k%length)

    for(let i =0;i<step;i++){
        const n = arr.pop()
        if(n){
            arr.unshift(n)
        }
    }
    return arr
}
const arr = [1,2,3,4,5,6,7,8]
const arr1 = rotate1(arr,3)
console.log(arr1)

运行结果

思路2:把数组拆分,最后concat拼接到一起

JavaScript Array slice() 方法

var fruits = ["Banana", "Orange", "Lemon", "Apple", "Mango"];
var citrus = fruits.slice(1, 3);

JavaScript 数组 Const

const array1 = ['a', 'b', 'c'];
const array2 = ['d', 'e', 'f'];
const array3 = array1.concat(array2);

console.log(array3);
// expected output: Array ["a", "b", "c", "d", "e", "f"]

TS代码

/**
 * 旋转数组K步 -使用concat
 * @param arr arr
 * @param k k
 * @returns arr
 */
function rotate2(arr:number[],k:number):number[]{
    const length = arr.length
    if(!k || length===0) return arr
    const step = Math.abs(k%length)

    const part1 = arr.splice(-step)
    const part2 = arr.splice(0,length-step)
    arr = arr.concat(part1,part2)
    return arr
}
const arr2 = [1,2,3,4,5,6,7,8]
const arr3 = rotate2(arr2,3)

console.log(arr3)

运行结果

三、总结:

分析代码,整理思路,尽量找出最优解,编写代码不仅要书写功能测试,而且要养成编写单元测试的习惯,保证程序的健壮性

复杂度分析:

  • 思路1的时间复杂度为O(n^2),空间复杂度为O(1)
  • 思路2的时间复杂度为O(1),空间复杂度为O(n)

前端重时间轻空间,思路2更佳

时间复杂度O(1)和O(n)差别很大

5. 数组是一个有序结构,数组的unshift、shirt、splice操作都很慢,pop和push都很快,.slice不会改变原数组,时间复杂度为0(1)

//性能测试
const arr4 = []
for(let i =0;i<10 * 10000;i++){
    arr4.push(i)
}
console.time('rotate1')
rotate1(arr4,9*10000)
console.timeEnd('rotate1')

const arr5 = []
for(let i=0;i< 10 * 10000;i++){
    arr5.push(i)
}
console.time('rotate2')
    rotate2(arr5,9*10000)
    console.timeEnd('rotate2')

四、划重点

  • 注意算法时间复杂度(前端重时间,轻空间)
  • 识破内置API的时间复杂度(如unshift为0(n))
  • 单元测试,考虑参数非法情况,提升代码健壮性

到此这篇关于JavaScript算法题之如何将一个数组旋转k步的文章就介绍到这了,更多相关JavaScript数组旋转k步内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • JS array 数组详解

    1.数组的声明方法 (1): arrayObj = new Array(); //创建一个数组. 复制代码 代码如下: var arr1 = new Array(); (2):arrayObj = new Array([size]) 创建一个数组并指定长度,注意不是上限,是长度. 复制代码 代码如下: var a = new Array(5); (3):arrayObj = new Array([element0[, element1[, ...[, elementN]]]]) 创建一个数组并赋

  • javascript 数组的定义和数组的长度

    本文提供一款简单的js入门教程,这是一款js数组定义与数组长度实例教程,如果你正在学习js数组的话,我们这里告诉你如何定义数组以及增加数组与数组长度计算实例. 先来看看如何定义数组 var a = new array(); var b = new array(8); var c = new array("first", "second", "third"); 或者数组直接量: 复制代码 代码如下: var d = ["first&quo

  • JavaScript算法题之如何将一个数组旋转k步

    目录 一.题目描述: 二.思路分析: 两种思路: 思路1:把末尾的元素挨个pop,然后unshift到数组后面 TS代码 运行结果 思路2:把数组拆分,最后concat拼接到一起 TS代码 运行结果 三.总结: 四.划重点 一.题目描述: 将一个数组旋转k步 输入一个数组[1,2,3,4,5,6,7,8] 当k=3时,即旋转3步 输出[6,7,8,1,2,3,4,5] 二.思路分析: 两种思路: 把末尾的元素挨个pop,然后unshift到数组后面 把数组拆分,最后concat拼接到一起 思路1

  • javascript算法题:求任意一个1-9位不重复的N位数在该组合中的大小排列序号

    具体题目是这样的: 从1--9中选取N个数字,组成不重复的N位数,从小到大进行编号,当输入其中任何一个数M时,能找出该数字对应 的编号.如 N=3,M=213.     输出:[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)]--->X=2 首先看到题目想到的是生成一个从少到大的全排列的数组,然后再遍历数组得到对应的序号(数组下标加1),又或者想到一个个从小到大的生成push进数组,然后判断该数是不是当前题目给的数,如果是的话要求的序号就是

  • javascript算法题 求任意一个1-9位不重复的N位数在该组合中的大小排列序号

    具体题目是这样的: 从1--9中选取N个数字,组成不重复的N位数,从小到大进行编号,当输入其中任何一个数M时,能找出该数字对应 的编号.如 N=3,M=213. 输出:[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)]--->X=2 首先看到题目想到的是生成一个从少到大的全排列的数组,然后再遍历数组得到对应的序号(数组下标加1),又或者想到一个个从小到大的生成push进数组,然后判断该数是不是当前题目给的数,如果是的话要求的序号就是当前数组

  • 浅谈js中字符和数组一些基本算法题

    最近在刷 fcc的题,跟升级打怪一样,一关一关的过,还挺吸引我的.今天抽时间把 Basic Algorithm Scritping  这部分题做了,根据一些提示,还是比较简单的.有些题的处理方式 方法,我想值得借鉴.比如在项目中有时候要处理一个字符,如果想不到一些相关的方法,还挺费事的,所以,在此记录下来,如果以后遇到一些字符或者数组处理,可以来翻翻这篇文章,希望以此得到一些提示而不是去翻文档. 看到此博文的博友,有更好更简单的代码或者好的想法,请留言交流(我一直觉得只有学习别人的优秀代码才能进

  • JavaScript将一个数组插入到另一个数组的方法

    本文实例讲述了JavaScript将一个数组插入到另一个数组的方法.分享给大家供大家参考.具体分析如下: 这段JS代码可以通过Array.prototype.push.apply方法将一个数组插入到另外一个数组,下面的代码将数组b插入到a var a = [4,5,6]; var b = [7,8,9]; Array.prototype.push.apply(a, b); uneval(a); // is: [4, 5, 6, 7, 8, 9] 希望本文所述对大家的javascript程序设计有

  • JS算法题之查找数字在数组中的索引位置

    前言 编写算法时,排序是一个非常重要的概念.它有各种各样的种类:冒泡排序.希尔排序.分块块排序,梳排序,鸡尾酒排序,侏儒排序 -- 这些可不是我瞎编的! 这个算法题能够让我们一睹精彩的世界.我们必须对数字数组进行升序排序,并找出给定数字在该数组中的位置. 算法说明 将值(第二个参数)插入到数组(第一个参数)中,并返回其在排序后的数组中的最低索引.返回的值应该是一个数字. 例如 getIndexToIns([1,2,3,4], 1.5) 应该返回 1,因为 1.5 大于 1(索引0),但小于 2(

  • JavaScript实现获取两个排序数组的中位数算法示例

    本文实例讲述了JavaScript实现获取两个排序数组的中位数算法.分享给大家供大家参考,具体如下: 题目 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 . 请找出这两个有序数组的中位数.要求算法的时间复杂度为 O(log (m+n)) . 你可以假设 nums1 和 nums2 不同时为空. 示例 1: nums1 = [1, 3] nums2 = [2] 中位数是 2.0 示例 2: nums1 = [1, 2] nums2 = [3, 4] 中位数是 (2 + 3)/

  • 实现Python3数组旋转的3种算法实例

    Python3实现旋转数组的3种算法 下面是Python3实现的旋转数组的3种算法. 一.题目 给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数. 例如: 输入: [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] 说明: 1.尽可能想出更多的解决方案,至少有三种不同的方法可以解

  • 面试常见的js算法题

    我们去面试一般都有笔试,笔试题一般都会涉及到很多算法的东西. 不管你用的多不多,反正就是要会.不然笔试很难过. 就算是直接面试的,有时候也会遇到面试官直接叫你当场写个算法题出来这种情况. 因为笔试时间很有限,不会出很复杂的题目,所以笔试怎么出都不会离开下面这几种题. 废话不多说,下面来列出主要的几个算法题. 1.排序 一般都是给个数组然后排序,有的从小到大,有的从大到小.一定要看清楚.以下都是从小到大的排序算法. 冒泡法 var arr = [3,6,1,2,5]; var temp; for(

  • JavaScript算法系列之快速排序(Quicksort)算法实例详解

    "快速排序"的思想很简单,整个排序过程只需要三步: (1)在数据集之中,选择一个元素作为"基准"(pivot). (2)所有小于"基准"的元素,都移到"基准"的左边:所有大于"基准"的元素,都移到"基准"的右边. (3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止. 举例来说,现在有一个数据集{85, 24, 63, 45,

随机推荐