JavaScript系列——数组元素左右移动N位算法实现

WrBug 发布于2019-08-22 13:52 / 3365人阅读

摘要：拆分法当我们没有具体思路的时候，就先假设数组移动位的情况。这里可以看成个数组，一个是没有到达边界的元素移动，一个是到达了边界的元素移动，当元素到达边界，就会往数组的初始位置移动，形成了一个循环的过程。

引言

在自己刚刚毕业不久的时候，去了一家公司面试，面试官现场考了我这道题，我记忆深刻，当时没有想到思路，毫无疑问被面试官当成菜鸟了。
最近刚好在研究数组的各种算法实现，就想到这道题，可以拿来实现一下，纪念自己逝去的青春。

需求

假设有这样一个数组

[1,2,3,4,5]

现在想要左移或者右移N位，比如移动1位

//左移1位
[2,3,4,5,1]

//右移1位
[5,1,2,3,4]

算法实现

这样一道题目，你先不要看我下面的代码，自己思考一下如何实现它，不管是复杂的还是简单的方法。
可以先告诉你我用了2行代码实现左、右移动元素。

拆分法 当我们没有具体思路的时候，就先假设数组移动1位的情况。

[1,2,3,4,5]
=>
[null,1,2,3,4] and [5,null,null,null,null]
=>
[5,1,2,3,4]

这里可以看成2个数组，一个是没有到达边界的元素移动[null,1,2,3,4]，一个是到达了边界的元素移动[5,null,null,null,null]，当元素到达边界，就会往数组的初始位置移动，形成了一个循环的过程。

很明显，如果我们将这2个移动后的数组合并起来，就是需求的结果。

移动2位

同样符合2个移动后的数组合并起来为结果的情况

[1,2,3,4,5]
=>
[null,null,1,2,3] and [4,5,null,null,null]
=>
[4,5,1,2,3]

刚好移动数组长度

[1,2,3,4,5]
=>
[1,2,3,4,5] and [] //如果没有，就假设为空数组

合并数组

假设移动1位的情况
上面的步骤，我们找到了规律，接下来要做的是找到2个数组，需要用到slice截取数组元素。
截取第一个数组

arr.slice(0,-1)
// [1,2,3,4]

截取第二个数组

arr.slice(-1)
// [5]

合并数组

arr.slice(-1).concat(arr.slice(0,-1))
// [5,1,2,3,4]

这样你就实现了移动1位的情况，接着，你继续拿+5和-5范围内的数字进行测试，发现都可以正常移动，当数字大于5或者小于-5的时候，代码就无效了，始终输出[1,2,3,4,5]

arr.slice(-6).concat(arr.slice(0,-6))
// [1,2,3,4,5]

我们再加上一个小技巧，求余数，假设是移动6，那么，实际上和移动1是相同的，我们就可以根据公式求余数

n = n%arr.length
// n = 6%5 余1

同理，当移动-6时

n = n%arr.length
// n = -6%5 余-1

接着带入公式，发现输出全部都正确了！！

思路分析完了，应该很清晰了吧，源码在下面、

算法源码

arr表示原始数组，n表示移动的距离，可以是正数、可以是0、也可以是负数、正数表示右移，负数表示左移，0表示不移动。

function moveElement(arr, n) {
  if(Math.abs(n)>arr.length) n = n%arr.length
  return arr.slice(-n).concat(arr.slice(0,-n))
}

// moveElement(arr, 9)
// moveElement(arr, 0)
// moveElement(arr, -9)

总结

下次面试要是继续碰到这道题，可能我又当场忘记思路了?

补充

看到有评论讨论不同方案的实现，这些都很厉害，没有唯一的答案，而思考解决方案的时候，要考虑的是时间复杂度，移动数组的元素都会造成数组的重新排列。

第一步方案我觉得应该是找到最小移动位置的代价，即移动2和移动2n是一样的，我们就只需要移动2，不需要再移动n，求余数的作用在于此，根据移动的位置切分出2个数组，不需要移动元素，最后我用的是concat合并2个数组，返回一个新的数组副本，这样就避免了移动元素。

还有一种方案是将2个数组使用new Set(array1)和new Set(array2)设置为集合，集合是key、value的散列表，可以用最少的代价移动位置，不导致重排，用集合移动完之后，再Array.from()转换回数组。

切忌，不要尝试去直接修改原数组的元素位置，这样做代价非常大，尤其是数组长度很长的时候！！

云服务器 GPU云服务器 javascript左右移动算法系列 javascript左右 js左右移动数据

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/92556.html

JavaScript 数据结构与算法之美 - 冒泡排序、插入排序、选择排序

摘要：之所以把冒泡排序选择排序插入排序放在一起比较，是因为它们的平均时间复杂度都为。其中，冒泡排序就是原地排序算法。所以冒泡排序是稳定的排序算法。选择排序思路选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，...

canger 2019-08-26 10:15 评论0 收藏0
JavaScript 数据结构与算法之美 - 十大经典排序算法汇总

摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。这应该是目前较为简单的十大经典排序算法的文章讲解了吧。比如原本在的前面，而，排序之后，在的后面十大经典排序算法冒泡排序思想冒泡排序只会操作相邻的两个数据。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法为王。想学好前端，先练好内功，内功不行，就...

zsy888 2019-08-26 10:27 评论0 收藏0
JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

摘要：之所以把归并排序快速排序希尔排序堆排序放在一起比较，是因为它们的平均时间复杂度都为。归并排序是一种稳定的排序方法。因此，快速排序并不稳定。希尔排序思想先将整个待排序的记录序列分割成为若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，只有内功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 评论0 收藏0