【Leetcode刷题】算法：删除有序数组中的重复项

梦里梦外; 2023-10-10 19:02 33阅读 0赞

#### 文章目录 ####

*  一、题目
 *  二、解答方法
 *   *  2.1 方法1
     *  2.2 方法2
 *  三、提交结果

## 一、题目 ##

![在这里插入图片描述][175fd8277ee74135b3e922d32b0bd235.png]

我们的示例为：

![在这里插入图片描述][072abfa56dfd4e778913509329a97585.png]

## 二、解答方法 ##

### 2.1 方法1 ###

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

这个解决方案使用了双指针的思想。指针 k 记录当前唯一元素的位置，初始值为 1，因为第一个元素必定是唯一的。我们遍历数组，当遇到与前一个元素不相同的元素时，将该元素放置在指针 k 的位置，并将 k 的值加 1。最后返回 k 的值即为唯一元素的数量。

你可以调用这个函数，传入你的升序数组 nums，它将返回新数组的长度以及唯一元素的数量。

### 2.2 方法2 ###

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

在优化后的代码中，我们将指针 k 的初始值设为 0。遍历数组时，如果当前元素 nums\[i\] 与指针 k 所指的元素 nums\[k\] 不相等，说明遇到了一个新的唯一元素，我们将其放置在指针 k 的下一个位置，并将 k 的值加 1。这样，我们只需要比较相邻的两个元素是否相等，避免了重复赋值操作，从而提高了时间效率。

这个优化方案是原地修改数组，没有使用额外的空间，因此在空间上也进行了优化。

1.  如果输入的列表 nums 长度为 0，即空列表，直接返回 0。
2.  初始化变量 k 为 0，用于记录唯一元素的位置。
3.  使用 for 循环遍历从 1 到 len(nums)-1 的范围，即遍历列表的第二个元素到最后一个元素。
4.  如果当前元素 nums\[i\] 与 nums\[k\] 不相等，表示遇到了一个新的唯一元素。将 k 值加 1，并将当前元素复制到 nums\[k\] 的位置。
5.  最后，返回 k + 1，即唯一元素的数量。

## 三、提交结果 ##

![在这里插入图片描述][a08e589b53ef4abeb1f4255fa45f6172.png]

[175fd8277ee74135b3e922d32b0bd235.png]: https://img-blog.csdnimg.cn/175fd8277ee74135b3e922d32b0bd235.png
[072abfa56dfd4e778913509329a97585.png]: https://img-blog.csdnimg.cn/072abfa56dfd4e778913509329a97585.png
[a08e589b53ef4abeb1f4255fa45f6172.png]: https://img-blog.csdnimg.cn/a08e589b53ef4abeb1f4255fa45f6172.png