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

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

一、题目内容

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

假设 nums 中不等于 $val$ 的元素数量为$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 = 0while(val in nums):for i in range(len(nums)):if nums[i] == val:k += 1for 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 实现思路

• 找到有多少个不用的元素
• 将所有$val$删掉
• 在删除后的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 算法实现

分成两个阶段

1. 前面：存储不等于$val$的元素
2. 后面：存储=$val$的元素

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

3.1.2 代码实现

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

3.1.3 代码分析

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

3.2 通用的

和26题目解法有关，还没有写到，等写到了再看吧

四、一些注意的地方

1. 多想一想双指针，用下来真的会方便好多