数组：删除数组中的元素

要求：原地删除，不是用额外的空间；

1. 原地删除指定元素

**输入：**nums = [0,1,2,2,3,0,4,2], val = 2 **输出：**5, nums = [0,1,4,0,3,,,_] **解释：**你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。 注意这五个元素可以任意顺序返回。 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

翻译下题目：

  1. 返回数组中不等于
    val
    的元素个数；
  2. 将数组中的
    val
    元素都放在数组最后；

因此考虑2个指针，

i寻找val
，
j从后向前寻找非val
；并在遍历的过程中，将
val
放到后面；

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i,j = 0, len(nums) - 1
        while i < j:
            if nums[i] == val:
                temp = nums[i]
                nums[i] = nums[j]
                nums[j] = temp
                j -= 1
            else:
                i += 1
        return i if len(nums) == 0 or nums[i] == val else i + 1

2. 有序数组中的重复项只出现1次

前提：有序数组，重复项只保留1个，原地

  • 因为有序，重复项都是连续的；
  • 修改后的数组也要保持有序；

双指针：

  • i：停留在不重复元素的末端；最终遍历完成，
    i
    指向的是完整的不重复数组的最后一个元素；
  • j：寻找与
    i
    不同的下一个元素； 
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i, j = 0, 0
        while j < len(nums):
            if nums[i] != nums[j]:
                i += 1
                nums[i] = nums[j]
            j += 1
        return i + 1

3. 有序数组中的重复项只出现2次

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        length = len(nums)
        if length <= 2:
            return length
        i, j = 2, 2
        while j < length:
            if nums[j] != nums[i - 2]:
                nums[i] = nums[j]
                i += 1
            j += 1
        return i

有序数组中的重复项只出现n次：

class Solution:
    def removeDuplicates(self, nums: List[int], time: int) -> int:
        length = len(nums)
        if length <= time:
            return length
        i, j = time, time
        while j < length:
            if nums[j] != nums[i - time]:
                nums[i] = nums[j]
                i += 1
            j += 1
        return i