Leetcode-Array-27.移除元素

发表于 分类于 ， 阅读次数： 本文字数： 515 阅读时长 ≈ 2 分钟

https://leetcode.cn/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150

思路

暴力解法

双重循环：每次找到一个 val ，就从前向后找到第一个不是 val 的数进行替换。

正向指针

上述暴力循环中，内层循环不必从头寻找，保留一个索引，每次从索引开始向后寻找

两侧双指针

因为我们只需要将非 val 数值存放在前半部分，不需要管后半部分是什么，所以我们可以使用双指针： - 指针1：从后向前，找到第一个非val 数 - 指针2：从前向后，找到第一个val数 - 进行交换，之后先移动指针1，再移动指针2，如果指针1与指针2相遇，结束

细节分析： 1. 全是非 val，指针2会在最后一个非val 位置碰上指针1。而凡是指针2碰上指针1，都是成功的，说明前面没有val 2. 如果是指针1碰上指针2，意味着非val 数没有在后半部分了。 3. 全是 val ，需要判断相遇处的值是不是val才能兼容前述情况。所以我们需要在“指针1与指针2相遇后”，判断一次值

上述分析乱七八糟，能看出来我今天状态不行。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        p=len(nums)
        if p == 0:
            return 0
        q,p=0,p-1
        # 相遇
        while p > q:
            while nums[p]== val and p >q: # 找从后向前第一个非 val
                p-=1
            while nums[q]!=val and  q <p: # 从前向后找到第一个 val
                q+=1
            # swqp
            temp = nums[q]
            nums[q]=nums[p]
            nums[p]=temp
        # 检查
        if nums[p]== val:
            return p
        else:
            return p+1

进一步优化代码，参考Leetcode官方题解，另外我的命名不太好，应该使用 right left：

我们更应该关注左侧的元素，应该首先从左向右找到 val:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0, right=nums.length;
        while(left < right){
            if(nums[left]==val){
                nums[left]=nums[right-1];
                right--;
            }else{
                left++;
            }
        }
        return left;
    }
}