[LeetCode] 27. Remove Element

轉自LeetCode

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

<Solution>

這題和 Remove Duplicates from Sorted Array 有點類似

差別在於，不再是 sorted array，然後要刪除的元素是可以指定的

最簡單的解法，可以用和 Remove Duplicates from Sorted Array 一樣思路

• 另外準備一個 index，然後歷遍 nums，如果不等於指定元素，就 copy 到 index 所在

code 如下

上面的解法會過，但整體速度會比較慢

因為做了很多不必要的 copy

例如 [1, 2, 3, 4]，指定刪除 4

在上面的解法，前面的 1, 2, 3 都會需要再 copy 一次

所以可以想個方法減少 copy 的數目(參考資料)

想法如下

• 把要刪除元素的丟到後面，同時把長度減少，不再去看那些元素，其餘的元素就不動

code 如下


kotlin