移除元素

来源 leetcode-27 移除元素

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

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

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

case1:

1
2

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]

case2:

1
2

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]

思路

稍微好一点的解法就是，通用的解法；

先设定变量 idx，指向待插入位置。idx 初始值为 0

然后从题目的「要求/保留逻辑」出发，来决定当遍历到任意元素 x 时，应该做何种决策：

如果当前元素 x 与移除元素 val 相同，那么跳过该元素。 如果当前元素 x 与移除元素 val 不同，那么我们将其放到下标 idx 的位置，并让 idx 自增右移。 最终得到的 idx 即是答案。

my ugly code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public class Solution
{
    public int RemoveElement(int[] nums, int val)
    {
        int currentIndex = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] != val)
            {
                nums[currentIndex] = nums[i];
                currentIndex++;
            }
        }

        return currentIndex;
    }
}

高手思路赏析

解题思路

根据题意，我们可以将数组分成「前后」两段：

前半段是有效部分，存储的是不等于 val 的元素。 后半段是无效部分，存储的是等于 val 的元素。 最终答案返回有效部分的结尾下标。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

大佬解法的精髓在于 swap(nums, i--, j--)，

碰到nums[i]==val就与最后一个进行交换，然后i--再检查一下交换来的值是不是等于val， 不保证原数组内容的顺序，当然也不要求保持顺序。

复杂度分析

  • 时间复杂度：O(n)，其中n为序列的长度。只需要遍历该序列至多一次。

  • 空间复杂度：O(1)，只需要常数的空间保存若干变量。