JavaScript系列——數組元素左右移動N位算法實現

WrBug 發布于2019-08-22 13:52 / 3391人閱讀

摘要：拆分法當我們沒有具體思路的時候，就先假設數組移動位的情況。這里可以看成個數組，一個是沒有到達邊界的元素移動，一個是到達了邊界的元素移動，當元素到達邊界，就會往數組的初始位置移動，形成了一個循環的過程。

引言

在自己剛剛畢業不久的時候，去了一家公司面試，面試官現場考了我這道題，我記憶深刻，當時沒有想到思路，毫無疑問被面試官當成菜鳥了。
最近剛好在研究數組的各種算法實現，就想到這道題，可以拿來實現一下，紀念自己逝去的青春。

需求

假設有這樣一個數組

[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左右移動數據

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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