# 27. Remove Element

### Leetcode

{% embed url="<https://leetcode.com/problems/remove-element/description/>" %}

### 題目

Given an integer array `nums` and an integer `val`, remove all occurrences of `val` in `nums` [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm). The relative order of the elements may be changed.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the **first part** of the array `nums`. More formally, if there are `k` elements after removing the duplicates, then the first `k` elements of `nums` should hold the final result. It does not matter what you leave beyond the first `k` elements.

Return `k` *after placing the final result in the first* `k` *slots of* `nums`.

Do **not** allocate extra space for another array. You must do this by **modifying the input array** [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) with O(1) extra memory.

**Custom Judge:**

The judge will test your solution with the following code:

```
int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}
```

If all assertions pass, then your solution will be **accepted**.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [3,2,2,3], val = 3
</strong><strong>Output: 2, nums = [2,2,_,_]
</strong><strong>Explanation: Your function should return k = 2, with the first two elements of nums being 2.
</strong>It does not matter what you leave beyond the returned k (hence they are underscores).
</code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [0,1,2,2,3,0,4,2], val = 2
</strong><strong>Output: 5, nums = [0,1,4,0,3,_,_,_]
</strong><strong>Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
</strong>Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).
</code></pre>

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一 - Two pointer**

這題需要排除等於 `val` 的數字，因此我們可以從頭開始遍歷，只要找到等於 `val` 的數字一律與矩陣後面的數字交換，這樣整個遍歷完後，不需要的數字都會放到後面了

這裡我們使用左指針與右指針的方式判斷，如果當下元素等於 `val` 就代表這個元素要與右指針的元素交換並且交換完後將右指針往前移動，那如果不等於 `val` 的話就將左指針往後移動

```javascript
/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    const swap = (i, j) => {
        const temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    let i = 0;
    let j = nums.length - 1;
    let output = 0;
    while(i <= j) {
        if (nums[i] === val) {
            // 如果元素等於 val => 與右指針所在的元素交換後，右指針往前移動
            swap(i, j);
            j--;
        } else {
            // 左指針向後移動
            i++;
            output++;
        }
    }

    return output;
};
```

Runtime: 63 ms Beats 10.20% of users with JavaScript

Memory: 49.13 MB Beats 17.43% of users with JavaScript

* **方法二**

當遇到要移除的元素時，繼續往後找後面不需移除的元素，並賦值到這個要被移除元素的 index 上

```javascript
var removeElement = function (nums, val) {
    let k = 0
    for (let i = 0; i < nums.length; i++) {
        // 如果元素不須移除，k 跟隨 i 一起加 1，
        // 否則的話讓 k 留在原地，i 往後找到不需移除的元素，並賦值到 k 上面
        if (nums[i] !== val) {
            nums[k] = nums[i]
            k += 1
        }
    }
    return k
};
```

Runtime: 57 ms Beats 34.56% of users with JavaScript

Memory: 48.86 MB Beats 55.86% of users with JavaScript

* **方法三 - Splice**

單純利用 js 的 splice 方法來移除元素

```javascript
var removeElement = function (nums, val) {
    for (let i = 0; i < nums.length; i++) {
        const value = nums[i];
        if (value === val) {
            nums.splice(i, 1);
            i--;
        }
    }

    return nums.length
};
```

Runtime: 57 ms Beats 34.56% of users with JavaScript

Memory: 48.86 MB Beats 55.86% of users with JavaScript

### 測資

```javascript
const nums = [0, 1, 2, 2, 3, 0, 4, 2], val = 2;
// const nums = [3,2,2,3], val = 3;
// const nums = [3,3], val = 3;
// const nums = [2], val = 3;

const result = removeElement(nums, val)
console.log(nums, result);
```
