題目描述

給定一個(gè)數(shù)組 nums 和一個(gè)值 val，你需要原地移除所有數(shù)值等于 val 的元素，返回移除后數(shù)組的新長度。

不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。

元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素。

解題思路

本題解題思路與上一篇的刪除有序數(shù)組重復(fù)元素類似，如下所示：

• 設(shè)定左右指針 i, j，變量 count 用于計(jì)數(shù)
• 指針 i 從左向右移動(dòng)，判斷元素是否等于 val；當(dāng)于 val 相等時(shí) count--, 并移動(dòng)指針 j，當(dāng)于 val 不等時(shí)指針 i 繼續(xù)向右移動(dòng)
• 當(dāng)指針 j 移動(dòng)時(shí)，判斷元素是否等于 val； 當(dāng)于 val 相等時(shí) count-- 繼續(xù)移動(dòng)指針 j, 當(dāng)不等時(shí)互換 i, j 元素并繼續(xù)移動(dòng)指針 i
• 當(dāng)指針 i，j 交匯時(shí)完成退出輪詢

可見如下圖示：

刪除元素

實(shí)現(xiàn)

public int removeElement(int[] nums, int val) {
    int i = 0, count = nums.length, j = count;

    while (true) {
        while (i < j) {
            if (nums[i] == val) {
                count--;
                break;
            } else {
                if (i + 1 == j) {
                    break;
                }

                i++;
            }
        }

        while (j > i) {
            j--;

            if (j == i) {
                break;
            }

            if (nums[j] == val) {
                count--;
            } else {
                nums[i] = nums[j];
                i++;
                break;
            }
        }

        if (i >= j) {
            break;
        }

    }

    return count;
}