26.删除有序数组中的重复项

题目链接

https://leetcode.cn/problems/remove-duplicates-from-sorted-array

解题思路

拷贝覆盖

根据题意, 给到的数组是非严格递增排列的, 所以相等的元素一定是连续排列的. 这就联想到双指针. 并且由于并不关注其余的元素, 所以可以直接把后面的元素拷贝到前面.

1. 初始化一个指针k, 指向数组的第一个元素的下标
2. 开始一个♻️, ♻️中的下标j为第二个指针
   • 若k和j所指向的元素不一致, 则k+1, 并将j所指向的元素拷贝到k自增后指向的元素
3. 返回唯一数组的长度为k+1

py

# ⌚ 45ms 📀 17.6MB
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k = 0
        for j in range(len(nums)):
            if nums[k] != nums[j]:
                k += 1
                nums[k] = nums[j]
        return k + 1

go

// ⌚ 4ms 📀 4.3MB
func removeDuplicates(nums []int) int {
    f := 0
    for _, v := range nums {
        if nums[f] != v {
            f++
            nums[f] = v
        }
    }
    return f + 1
}

字典

字典法相对来说适应性更加好, 因为它不需要这个数组是递增或递减的, 随便一个数组过来都能够输出唯一的数组.

1. 初始化一个字典dict, 一个存有重复元素下标的数组index, 代表重复元素个数的值k
2. 开始一个♻️
   • 如果当前下标指向的元素不在dict里面的话, 放到dict里面, k+1
   • 如果当前下标指向的元素在dict里面的话, 将当前的下标放到index里面
3. 开始一个♻️
   • 将index数组里面所有下标指向的元素都pop掉
4. 返回唯一数组长度为k

Python批量移除数组元素的方法请见这里.

py

# ⌚ 43ms 📀 19.2MB
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        dict = {}
        k = 0
        index = []
        for i in range(len(nums)):
            if nums[i] not in dict:
                dict[nums[i]] = 0
                k += 1
            else:
                index.append(i)
        for ind in sorted(index, reverse=True):
            nums.pop(ind)
        return k

go

// ⌚ 7ms 📀 4.8MB
func removeDuplicates(nums []int) int {
    k := 0
    dic := make(map[int]struct{})
    numsNew := make([]int, 0, len(nums))
    for _, v := range nums {
        _, ok := dic[v]
        if ok {
        } else {
            dic[v] = struct{}{}
            numsNew = append(numsNew, v)
            k++
        }
    }
    copy(nums, numsNew)
    return k
}

滑动窗口

这是一种通用解法, 请看这里.