「双指针」LeetCode 26(删除有序数组中的重复项)

警告
本文最后更新于 2023-01-23,文中内容可能已过时。

Leetcode 26 题

题干简述

  1. 给定:一数组,该数组有序且有重复元素。
  2. 要求:返回下标L,要求数组num[0,L]内元素单调递增且不重复。

详情请看:https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

解题思路:双指针算法

  1. 右指针遍历数组
  2. 右指针碰到新元素时,将其移动到左指针处。
  3. 因为数组有序,所以当nums[r] != nums[r-1]时意味着出现新元素。

图解算法

/leetcode/leetcode_26/1.png

/leetcode/leetcode_26/2.png

/leetcode/leetcode_26/3.png

/leetcode/leetcode_26/4.png

/leetcode/leetcode_26/5.png

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if (len(nums) == 0):
            return 0

        l = 0
        for r in range(1, len(nums)):
            if (nums[r] != nums[r-1]):
                l += 1
                nums[l] = nums[r]

        return l+1

总结

LeetCode 26题是一道简单题,利用双指针算法可以轻松解决。

技巧

利用 nums[r] != nums[r-1] 判断元素是否为新元素是此题的核心。

如果不多留心,很可能写成nums[r] != nums[l]

Buy me a coffee~
室长 支付宝支付宝
室长 微信微信
0%