27. Remove Element

Leetcode

Remove Element - LeetCodeLeetCode

題目

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. 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 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.

Example 1:

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

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
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).

解答

• 方法一 - Two pointer

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

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

/**
 * @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 上

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 方法來移除元素

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

測資

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);