[演算法題目] Move Element To End

本題資訊

難度：easy
使用語言：C++
相關概念：Arrays

---

題目敘述

You’re given an array of integers and an integer. Write a function that moves all instances of that integer in the array to the end of the array and returns the array.

The function should perform this in place (i.e., it should mutate the input array) and doesn’t need to maintain the order of the other integers.

Input:
array = [2, 1, 2, 2, 2, 3, 4, 2]
toMove = 2

Output:
[1, 3, 4, 2, 2, 2, 2, 2]

很好，這次題目也是簡潔有力的類型。給定一個陣列，並將指定的數字通通搬到後面去。

---

Idea 1

把指定的數字全部搬到後面，聞起來有 swap 的味道，大概是目前巡覽到的數字若等於 toMove，二話不說直接丟去後面就可以了。

如果照這樣的方式，就會用到 array 問題處理中很常運用的雙頭進行。頭尾各設定 index 為 i 和 j，先判斷 index 為 j 的那個元素，若等於 toMove 則代表不用動它，j 繼續往前走，直到遇到的數字不等於 toMove 便停下來。

而 index 為 i 的那個元素，若遇到等於 toMove 的話，要停下來且和第 j 個元素交換，交換後繼續往後走。以上過程重複持續到 i 大於等於 j 為止。

#include <vector>

using namespace std;

vector<int> moveElementToEnd(vector<int> array, int toMove) {
  int i = 0, j = array.size() - 1;
  while (i < j) {
    while (i < j && array[j] == toMove){
      j--;
    }
    if (array[i] == toMove){
      swap(array[i], array[j]);
    }
    i++;
  }
  return array;
}

時間複雜度：\(O(n)\)，\(n\) 指的是 input 的大小。
空間複雜度：\(O(1)\)

Idea 2

其實不太算第二個想法，因為大致上和第一個想法一樣。這個做法算是不管後端第 j 個走過來的元素有沒有符合 toMove，只管從頭走過去的有沒有等於 toMove，有的話就往後丟（交換）。所以有可能會有明明 2 已經好好待在最後面了，但還是跟另外一個 2 交換被丟去前面的狀況。

#include <vector>

using namespace std;

vector<int> moveElementToEnd(vector<int> array, int toMove) {
  int i = 0, j = array.size() - 1;
  while (i < j){
    if (array[i] != toMove)
      i++;
    else {
      swap(array[i], array[j]);
      j--;
    }
  }
  return array;
}

時間和空間複雜度應該和 Idea 1 一樣。