What is the most efficient way to remove duplicates from a sorted array?

Using a two-pointer approach where one pointer tracks the position to write unique elements and the other scans for new values.

Do I need extra space to remove duplicates in this problem?

No, the problem requires in-place modification with O(1) extra space using the two-pointer invariant method.

How does the array being sorted simplify removing duplicates?

Since duplicates are consecutive, you only need to compare each element with the previous unique value to detect duplicates.

What should be returned after removing duplicates?

Return the number of unique elements, with the first k positions of the array containing these values in order.

Can this two-pointer pattern be adapted for allowing multiple occurrences?

Yes, by adjusting the write pointer logic and invariant, you can allow up to a fixed number of duplicates while scanning.

#26

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

删除有序数组中的重复项

给你一个非严格递增排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。考虑 nums 的唯一元素的数量为 k 。去重后，返回唯一元素的数量 k 。 nums 的前 k…

数组双指针

题目描述

给你一个 非严格递增排列 的数组 nums ，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持一致。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k。去重后，返回唯一元素的数量 k。

nums 的前 k 个元素应包含 排序后 的唯一数字。下标 k - 1 之后的剩余元素可以忽略。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被通过。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4,_,_,_,_,_]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

1 <= nums.length <= 3 * 10⁴
-100 <= nums[i] <= 100
nums 已按 非递减 顺序排列。

lightbulb

解题思路

方法一：一次遍历

我们用一个变量 $k$ 记录当前已经处理好的数组的长度，初始时 $k=0$ ，表示空数组。

然后我们从左到右遍历数组，对于遍历到的每个元素 $x$ ，如果 $k=0$ 或者 $x \neq nums[k-1]$ ，我们就将 $x$ 放到 $nums[k]$ 的位置，然后 $k$ 自增 $1$ 。否则， $x$ 与 $nums[k-1]$ 相同，我们直接跳过这个元素。继续遍历，直到遍历完整个数组。

这样，当遍历结束时， $nums$ 中前 $k$ 个元素就是我们要求的答案，且 $k$ 就是答案的长度。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为数组的长度。

补充：

原问题要求最多相同的数字最多出现 $1$ 次，我们可以扩展至相同的数字最多保留 $k$ 个。

由于相同的数字最多保留 $k$ 个，那么原数组的前 $k$ 个元素我们可以直接保留；
对于后面的数字，能够保留的前提是：当前数字 $x$ 与前面已保留的数字的倒数第 $k$ 个元素比较，不同则保留，相同则跳过。

相似题目：

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

1

2

3

4

5

6

7

8

9

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

speed

复杂度分析

指标	值
时间	complexity is O(n) since each element is processed once by the scanning pointer. Space complexity is O(1) as all operations are in-place without additional data structures.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checks if you recognize the array is sorted and duplicates are consecutive.
question_mark
Watches whether you properly maintain the two-pointer invariant without extra memory.
question_mark
Assesses handling of edge cases like empty arrays or arrays with all identical elements.

warning

常见陷阱

外企场景

error
Overwriting unique elements when the write pointer is incremented incorrectly.
error
Using extra arrays, violating the in-place constraint.
error
Failing to return the correct count of unique elements while only modifying the array partially.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Remove duplicates allowing at most two occurrences instead of one, requiring adjusted invariant logic.
arrow_right_alt
Apply the same approach to a sorted linked list instead of an array.
arrow_right_alt
Handle arrays sorted in descending order, requiring reversed comparisons but same two-pointer logic.

help

常见问题

外企场景

继续练习

#27 移除元素 #31 下一个排列 #18 四数之和