day2 移除元素[双指针/栈的思维] 26.9.16

[数组] 27. 移除元素 / Easy / ⚠️

题目:

卡点：

1. 我刚开始的时候没有反应过来这个题目的含义是让不等val的元素替代原有索引位置,所以想了好久没想到解决方法,后面想到了用pop方法删除元素

2. 使用pop过程中我忘记了len返回的是list的长度,而索引是长度减一的

3. 后面学习了题解发现这题可以用两种思路解决,不需要用到list.pop

   1. 栈思维,使用for循环遍历,用后进入的数值替代前面的数字

   2. 双指针,单独开个变量代替for循环进行遍历,另一个变量作为索引用于覆盖

核心套路：

• 栈思维:新元素覆盖旧元素

它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对的，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

• 双指针:两变量分别移动

双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息．

代码：

初始使用pop,while循环

▼
Python
复制代码
class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        #更改nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素
        #考虑下for遍历
        #for遍历我不知道怎么和索引结合,我尝试while循环   #使用range其实可以用range循环
        #使用了pop方法
        k=0
        a=0
        while a <= len(nums)-1:
            if nums[a] == val:
                nums.pop(a)
                
            else:
                k+=1
                a+=1    
        return k

for循环,栈思维

▼
Python
复制代码
class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        #使用栈的思考,能大大简化
        k = 0
        for a in nums :
            if a != val:
                nums[k] = a
                k +=1
        return k
                

While循环,双指针

▼
Python
复制代码
class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        #本次尝试双指针
        a,b = 0,0
        #本质上是用一个指针代替了for的功能
        while a<len(nums):
            if nums[a] != val:
                nums[b]= nums[a]
                b+=1
            a+=1
        return b

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

二刷记录：

• [ ]