【leetcode刷题】面试经典150题 , 27. 移除元素

leetcode刷题
面试经典150
27. 移除元素
难度：简单

文章目录

一、题目内容
二、自己实现代码
- 2.1 方法一：直接硬找
- - 2.1.1 实现思路
  - 2.1.2 实现代码
  - 2.1.3 结果分析
- 2.2 方法二：排序整体删除再补充
- - 2.1.1 实现思路
  - 2.1.2 实现代码
  - 2.1.3 结果分析
三、官方解法
- 3.1 双指针
- - 3.1.1 算法实现
  - 3.1.2 代码实现
  - 3.1.3 代码分析
- 3.2 通用的
四、一些注意的地方

一、题目内容

给你一个数组 nums 和一个值 $v a l$ ，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 $v a l$ 的元素数量为 $k$ ，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 $k$ 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回不相等的元素数 $k$

二、自己实现代码

2.1 方法一：直接硬找

2.1.1 实现思路

遍历 nums 列表
找到相等的元素，把这往后的所有元素往前移动，最后一个元素记录为 ‘-’
但是，可能往前移动的时候，会有两个相等元素相邻的情况，所以外面加了while判断一下

2.1.2 实现代码

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        k = 0
        while(val in nums):
            for i in range(len(nums)):
                if nums[i] == val:
                    k += 1
                    for j in range(len(nums)-i-1):
                        nums[i+j] = nums[i+j+1]
                    nums[len(nums)-k] = "-"
        return len(nums) - k

2.1.3 结果分析

在这里插入图片描述

时间复杂度：O(n^2)
空间复杂度：O(1)

2.2 方法二：排序整体删除再补充

2.1.1 实现思路

找到有多少个不用的元素
将所有 $v a l$ 删掉
在删除后的nums上补充“-”

2.1.2 实现代码

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        nums.sort()
        diff = len(nums) - nums.count(val)
        while val in nums:
            nums.remove(val)
        for i in range(diff):   
            nums.append("-")
        return diff

2.1.3 结果分析

在这里插入图片描述

三、官方解法

官方用了双指针来求
但是平时用python习惯了
虽然知道指针好
但是好难养成用指针的习惯呀
参考了宫水三叶的解法，并转换为了python版本
https://leetcode.cn/problems/remove-element/solutions/575555/shua-chuan-lc-shuang-bai-shuang-zhi-zhen-mzt8/

3.1 双指针

3.1.1 算法实现

分成两个阶段

前面：存储不等于 $v a l$ 的元素
后面：存储= $v a l$ 的元素

直接一个新的 $j$ ，相等的跳过，不相等的往下填写到数组里进行覆盖

3.1.2 代码实现

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        j = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[j] = nums[i]
                j += 1
        return j