【LittleDuck_LeetCodeNote】27 - Remove Element

Question and Hints:

• Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
• Return k.

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];
}

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

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

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

First Solution

💡 這題的思路是參考Quick Sort的作法：兩個索引 i 和 j，
i 從前面往後數尋找應該刪除的值，
j 從後面往前數尋找未被刪除的值，
將所有與val相同的值丟到陣列後面，
最後從頭檢查，直到發現val為止，
如此就能得到新的陣列與長度。

class Solution {
    public int removeElement(int[] nums, int val) {
        // except: nums.len<2
        if(nums.length == 0 || nums.length == 1 && nums[0] == val)
            return 0;
        
        int i=0, j=nums.length-1;
        int temp;

        while(i < j){
            if(nums[i] == val){
                while(i < j && nums[j] == val){
                    j--;
                    if(i >= j)
                        return i;
                    if(j <= -1)
                        return 0;
                }
                temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
                j--;        
            }
            i++; 
        }

        int k = 1;
        for(; k<nums.length; k++){
            if(nums[k] == val)
                break;
        }

        return k;
    }
}

Upgrade Solution

💡 思路是相似的，只是它在index的用途不同：
兩個index都是由前往後數，
i 負責尋找未被刪除的值，
j 負責尋找應該刪除的值，
然後不做交換，而是直接取代裡面的值。

可以換個角度想像兩個索引的工作：
i 往前尋找新陣列的值，
j 鎖定在新陣列的最尾端，
一旦 i 找到值，就從陣列最尾端塞進去。

class Solution {
    public int removeElement(int[] nums, int val) {
        int j=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=val){
                nums[j++]=nums[i];
            }
        }
        return j;
    }
}