在自己刚刚毕业不久的时候,去了一家公司面试,面试官现场考了我这道题,我记忆深刻,当时没有想到思路,毫无疑问被面试官当成菜鸟了.
最近刚好在研究数组的各种算法实现,就想到这道题,可以拿来实现一下,纪念自己逝去的青春.
需求
假设有这样一个数组
[1,2,3,4,5]
现在想要左移或者右移 N 位,比如移动 1 位
算法实现
//左移1位
[2, 3, 4, 5, 1]
//右移1位
[5, 1, 2, 3, 4]
这样一道题目,你先不要看我下面的代码,自己思考一下如何实现它,不管是复杂的还是简单的方法.
可以先告诉你我用了 2 行代码实现左,右移动元素.
拆分法
当我们没有具体思路的时候,就先假设数组移动 1 位的情况.
这里可以看成 2 个数组,一个是没有到达边界的元素移动 [null,1,2,3,4],一个是到达了边界的元素移动 [5,null,null,null,null],当元素到达边界,就会往数组的初始位置移动,形成了一个循环的过程.
[1,2,3,4,5]
=>
[null,1,2,3,4] and [5,null,null,null,null]
=>
[5,1,2,3,4]
很明显,如果我们将这 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]
这样你就实现了移动 1 位的情况,接着,你继续拿 + 5 和 - 5 范围内的数字进行测试,发现都可以正常移动,当数字大于 5 或者小于 - 5 的时候,代码就无效了,始终输出 [1,2,3,4,5]
arr.slice(-1).concat(arr.slice(0,-1))
// [5,1,2,3,4]
我们再加上一个小技巧,求余数,假设是移动 6,那么,实际上和移动 1 是相同的,我们就可以根据公式求余数
arr.slice(-6).concat(arr.slice(0,-6))
// [1,2,3,4,5]
同理,当移动 - 6 时
n = n%arr.length
// n = 6%5 余1
接着带入公式,发现输出全部都正确了!!
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)
下次面试要是继续碰到这道题,可能我又当场忘记思路了
来源: https://segmentfault.com/a/1190000012882330