problem

輸入為一個元素皆為整數的陣列，以及一個整數 k，將所有陣列中為 k 的元素移動到末尾，並回傳陣列。
題目要求原地進行，也就是需直接操作輸入陣列。其他不為 k 的元素不用保持原本順序。

sample input:
array = [2, 1, 2, 2, 2, 3, 4, 2, 2]
k = 2

sample output:
[1, 3, 4, 2, 2, 2, 2, 2, 2] // 1, 3, 4 的順序不拘

解析中提到看完這個題目後，對於時間表現可能可以有一個直覺，就是預期應該要找到 O(n) 時間的解法。

想法的流程是，看完題目可能會先想到排序，這樣蠻容易找到所有為 k 的元素，但需要 O(nlogn) 時間，而且面試應該不會這麼簡單。而如果利用其他方法或任何資料結構來輔助，總會需要遍歷過陣列一次，就需要 O(n) 時間。如果還想要再快一點，例如追求 O(logn)，那就要想辦法用到二元搜尋，而且二元搜尋也是需要排序。所以討論到這裡，可以以 O(n) 為理想目標來解題。

因為題目提到原地操作，所以可以思考利用交換元素的方式，達到線性執行時間。
步驟是：

1. 以兩個指標 (left, right) 分別指向陣列開頭及末尾數字。
   [2, 1, 2, 2, 2, 3, 4, 2, 2]
2. 若 left 不為 k，則將指標持續右移；若 right 為 k 則將指標持續向左移。
   例如此時 left 為 2，所以不動；right 為 2，所以向左移，直到指向 4。
3. 直到碰到 left 為 k，且 right 不為 k (代表兩個數字都在不正確的位置)，交換兩個數字。
4. 在左右指標不重疊的情況下，重複步驟 2-3，最後回傳陣列。

n 為陣列長度
time: O(n)
space: O(1)

關於中間判斷指標及交換的部分，在程式碼上應該有不同的表達方式。例如可以兩端都先向內移動到正確的位置，再進行交換 (5-7 行)，或是移動指標再搭配判斷 (9-11 行註解起來的部分)。另外也可以每個指標位置都用判斷式。

重點在於指標向內移動，並且兩端都要找到需要交換的數字。另外可以特別注意的部分是內層判斷如果使用 while 迴圈也要加上 left < right 的條件，否則可能會出現內層指標已經重疊卻持續更新的錯誤。

function moveElementToEnd(array, k) {
  let i = 0;
  let j = array.length - 1;
  while (i < j) {
    while (i < j && array[j] === k) j--;
    while (i < j && array[i] !== k) i++;
    swap(array, i, j);
    /*
    while (i < j && array[j] === k) j--;
    if (array[i] === k) swap(array, i, j);
    i++
    */
  }
  return array;
}

function swap(ary, i, j) {
  let temp = ary[i];
  ary[i] = ary[j];
  ary[j] = temp;
}