27. 移除元素

转载自Leet Code

题目描述

给你一个数组nums和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用\(O(1)\)额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例1: >输入：nums = [3,2,2,3], val = 3 >输出：2, nums = [2,2] >解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例2: >输入：nums = [0,1,2,2,3,0,4,2], val = 2 >输出：5, nums = [0,1,4,0,3] >解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

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

---

我的代码

\(T(N) = O(N)\), \(S(N) = O(1)\)

{.line-numbers}

class MySolution27
{
    public int removeElement(int[] nums, int val) 
    {
    	int move  = 0;
    	for (int i=0; i<nums.length; i++)
    	{
            if (nums[i]==val)
            {
                move++; continue;
            }
            nums[i-move] = nums[i];
    	}
    	return nums.length-move;
    }
}

---

方法一：双指针

\(T(N) = O(N)\), \(S(N) = O(1)\)

i为快指针，j为慢指针。 当nums[j]=val时，递增j跳过该元素，i不动。 当nums[j]≠val时，就将nums[j]复制到nums[i]，并同时递增i和j。 直到j到达数组末尾，则新数组长度为i。

假设数组总共有 n 个元素，i 和 j至少遍历 2n 步。

{.line-numbers}

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

---

方法二：双指针 - 当要删除的元素很少时

\(T(N) = O(N)\), \(S(N) = O(1)\)

现在考虑数组包含很少的要删除的元素的情况。 例如，num=[1，2，3，5，4]，val=4。 之前的算法会对前四个元素做不必要的复制操作。 另一个例子是 num=[4，1，2，3，5]，val=4。 似乎没有必要将 [1，2，3，5] 这几个元素左移一步，因为问题描述中提到元素的顺序可以更改。

当我们遇到 nums[i] = val 时， 我们可以将当前元素与最后一个元素进行交换，并释放最后一个元素。 这实际上使数组的大小减少了 1。

请注意，被交换的最后一个元素可能是您想要移除的值。 但是不要担心，在下一次迭代中，我们仍然会检查这个元素。

在这个方法中，赋值操作的次数等于要删除的元素的数量。 因此，如果要移除的元素很少，效率会更高。

{.line-numbers}

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