LeetCode日积月累：02.移除元素
根据代码随想录的讲解顺序开始打卡学习，闲时更新。
代码随想录：https://www.programmercarl.com/0027.移除元素.html#_27-移除元素
LeetCode练习题目：https://leetcode-cn.com/problems/remove-element/
题目描述
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例
1
2
3
| 输入：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]，也会被视作正确答案。
|
1
2
3
4
| 输入：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。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
|
解决方案（own）
借本想法是建立前、后两个指针，前指针从前往后判断元素是否是移除，在发现需要移除的值后，后指针从后往前遍历寻找不等于val的元素，然后交换这两个指针对应的元素值。整个程序在前指针大于后指针时停止。算法总共只需遍历一次数组元素，时间复杂度为O(n)。
每次前后指针找到待移除元素时，数组总长度-1；该方法会改变删除后输出数组元素的相对位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
l = len(nums)
left_idx, right_idx = 0, l-1
temp = None
while left_idx <= right_idx:
if nums[left_idx] == val:
l -= 1
while nums[right_idx] == val and left_idx < right_idx :
right_idx -= 1
l -= 1
temp = nums[left_idx]
nums[left_idx] = nums[right_idx]
nums[right_idx] = temp
right_idx -= 1
left_idx += 1
return l
|
解决方案（others）
双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
快慢指针均从前往后遍历， 当快指针遇到待删除元素时，慢指针暂停移动，快指针继续遍历，直到遇到非删除元素，然后将快指针对应的值赋值到慢指针所在位置，赋值后慢指针和快指针继续移动，最终到快指针遍历结束，此时慢指针的位置则为移除val后的数组长度。
因为是顺序遍历，最后输出的数组元素之间的相对位置与删除前一致。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution:
"""双指针法
时间复杂度：O(n)
空间复杂度：O(1)
"""
@classmethod
def removeElement(cls, nums: List[int], val: int) -> int:
fast = slow = 0
while fast < len(nums):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
|