旭的小窝

27. Remove Element

 
  • 2023年 06月08日

Promble

link: https://leetcode.com/problems/remove-element/description/

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums. Return k.

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Approach 1

Thought

  1. 遍历nums，比较nums[i] == val
    1. 如果相等，将位置元素替换为’_’
  2. 循环移除’_’
  3. 返回的k值是nums中剩余元素的长度

Code

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        for i in range(len(nums)):
            if nums[i] == val:
                nums[i] = '_'
        print(nums)
        while '_' in nums:
            nums.remove('_')
        print(nums)
        return len(nums)

Complexity

时间复杂度

  • 遍历 $O(n)$
  • 移除 $O(n)$
  • 总时间复杂度： $O(n) + O(n) = O(n)

Approach 2

快慢指针的方法

Thought

  1. 定义慢指针 slowIndex = 0
  2. 使用快指针遍历nums，fastIndex
  3. 判断，如果val!=fastIndex
  4. nums[slowIndex] = nums[fastIndex]
  5. 更新slowIndex+=1
  6. 返回slowIndex的长度，即为最后数组的长度 这样做，队列的头部（前面）是有序的，虽然会覆盖原来的值，但是从前面开始排序，所以即使覆盖了也没有关系。

Code

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slowIndex = 0
        for i in range(len(nums)):
            if (val != nums[i]):
                nums[slowIndex] = nums[i]
                slowIndex += 1 

        return slowIndex

Approach 3

从后面往前比较

Thought

  1. j记录最后的元素位置
  2. i从后面往前遍历nums
  3. 如果i的位置==val
    1. A[i], A[j] = A[j], A[i]
    2. j -= 1
  4. 返回j+1

这个方法和Approach 2的方法很相似，只不过写法不一样

Code

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        j = len(nums) - 1
        for i in range(len(nums)-1, -1, -1):
            if nums[i] == val:
                nums[i], nums[j] = nums[j], nums[i]
                j -= 1

        return j+1
搜索