AI毛毛的blog

leetcode打卡-0026删除数组中重复项

题目描述

给你一个有序数组nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array

解题思路

1. 双指针

按照正常思维思考这题，可以划分一个额外的临时数组tmp，从头遍历原始数组nums，不断地比较，将新元素放进tmp里，不过题目要求原地删除，所以需要简单修改一下，将新元素直接放到原始nums里去，占用以前元素的位置。

用一个慢指针slow指向有效数组的最后一个位置，用来记录不重复数组的尾部，用一个快指针fast顺序遍历数组。

当fast与slow所指的值不一致时，证明这是两个不重复元素，将slow后一位的值改为fast指向的值，slow前进一位，fast继续遍历即可，最后返回长度即为slow+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Python实现

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if nums == []:
            return 0
        
        i = 0
        length = len(nums)
        for j in range(1, length):
            if nums[i] != nums[j]:
                i += 1
                nums[i] = nums[j]
        return i + 1

顺便练习一下Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
impl Solution {
    pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
        if nums.is_empty() {
            return 0;
        }

        let mut i = 0;
        for j in 1..nums.len() {
            if nums[i] != nums[j] {
                i += 1;
                nums[i] = nums[j];
            }
        }
        i as i32 + 1
    }
}

2. 通用套路思维

如果将原问题的「最多保留1位」修改为「最多保留k位」，问题会更有通用性，例如leetcode第80题。

这个想法来自于宫水三叶的题解，很巧妙，此处参考引证一下。

  • 由于是保留k个相同数字，对于前k个数字，我们可以直接保留。
  • 对于后面的任意数字，能够保留的前提是：与当前写入的位置前面的第k个元素进行比较，不相同则保留。

第一条很好理解，因为这是有序数组，所以前k个元素里，每种数字都会符合不超过k个的条件；第二条，就是反向思考，一个数字与写入位置的第前k个元素对比，如果相同，证明写入位置之前已经写满了k个当前元素，那么写入位置就需要寻找一个新元素写入了，如果不同，就把当前元素复制过去补位。

所以，通用的Python实现代码如下：

1
2
3
4
5
6
7
8
9
10
def process(nums, k):
    # idx记录最初的写入位置，直接保留了前k位
    idx = k

    # 从第k位往后遍历，判断是否满足上面的第二条推定
    for x in nums[k:]:
        if nums[idx-k] != x:
            nums[idx] = x
            idx += 1
    return idx

总结

双指针的方法很容易想到，在处理字符串问题是比较常用，不过后面的通用解法，它是建立在“数组有序”且“保留逻辑”的基础上，可以作为解决这种字符串问题的套路尝试。