LeetCode 26: Remove Duplicates from Sorted Array (Two Pointers Write Index)
LeetCode 26ArrayTwo PointersToday we solve LeetCode 26 - Remove Duplicates from Sorted Array.
Source: https://leetcode.com/problems/remove-duplicates-from-sorted-array/
English
Problem Summary
Given a non-decreasing integer array nums, remove duplicates in-place so that each unique element appears once in the prefix. Return k, the number of unique elements. The first k positions must contain the final unique values in original sorted order.
Key Insight
Because the array is sorted, duplicates are adjacent. So we only need to compare current value with the last accepted unique value. Maintain a write index k for the next unique slot.
Brute Force and Why Insufficient
A brute-force approach could build a new list/set and then copy back. It uses extra memory and ignores the in-place constraint. The optimal solution writes directly into nums while scanning once.
Optimal Algorithm (Step-by-Step)
1) If nums is empty, return 0.
2) Initialize k = 1; the first element is always unique.
3) For each index i from 1 to n-1, compare nums[i] with nums[k-1].
4) If different, assign nums[k] = nums[i] and increment k.
5) Return k.
Complexity Analysis
Time: O(n).
Space: O(1) extra space.
Common Pitfalls
- Comparing with nums[i-1] after overwrites instead of nums[k-1].
- Forgetting to handle empty array.
- Returning array length instead of unique count k.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int k = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[k - 1]) {
nums[k] = nums[i];
k++;
}
}
return k;
}
}func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
k := 1
for i := 1; i < len(nums); i++ {
if nums[i] != nums[k-1] {
nums[k] = nums[i]
k++
}
}
return k
}class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.empty()) return 0;
int k = 1;
for (int i = 1; i < (int)nums.size(); i++) {
if (nums[i] != nums[k - 1]) {
nums[k] = nums[i];
k++;
}
}
return k;
}
};class Solution:
def removeDuplicates(self, nums: list[int]) -> int:
if not nums:
return 0
k = 1
for i in range(1, len(nums)):
if nums[i] != nums[k - 1]:
nums[k] = nums[i]
k += 1
return kvar removeDuplicates = function(nums) {
if (nums.length === 0) return 0;
let k = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== nums[k - 1]) {
nums[k] = nums[i];
k++;
}
}
return k;
};中文
题目概述
给定一个非递减数组 nums，要求你原地删除重复元素，使每个不同元素只出现一次，并返回去重后元素个数 k。数组前 k 个位置必须是最终结果，顺序保持不变。
核心思路
数组有序意味着重复值一定连续出现。我们维护写指针 k，表示下一个“新元素”要写入的位置；只要当前值和最后一个已写入值 nums[k-1] 不同，就写入并前进。
朴素解法与不足
朴素做法是先用新数组或集合去重，再复制回原数组。这会额外占用空间，不满足题目强调的原地修改。更优做法是一趟扫描、原地覆盖。
最优算法（步骤）
1）若数组为空，返回 0。
2）初始化 k = 1，首元素天然保留。
3）从 i = 1 遍历到末尾，比较 nums[i] 与 nums[k-1]。
4）若不同，则执行 nums[k] = nums[i]，并让 k++。
5）遍历结束返回 k。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)（额外空间）。
常见陷阱
- 覆盖写入后仍拿 nums[i-1] 比较，导致判断错误。
- 忽略空数组边界。
- 返回值写成数组长度而不是去重后的 k。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int k = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[k - 1]) {
nums[k] = nums[i];
k++;
}
}
return k;
}
}func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
k := 1
for i := 1; i < len(nums); i++ {
if nums[i] != nums[k-1] {
nums[k] = nums[i]
k++
}
}
return k
}class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.empty()) return 0;
int k = 1;
for (int i = 1; i < (int)nums.size(); i++) {
if (nums[i] != nums[k - 1]) {
nums[k] = nums[i];
k++;
}
}
return k;
}
};class Solution:
def removeDuplicates(self, nums: list[int]) -> int:
if not nums:
return 0
k = 1
for i in range(1, len(nums)):
if nums[i] != nums[k - 1]:
nums[k] = nums[i]
k += 1
return kvar removeDuplicates = function(nums) {
if (nums.length === 0) return 0;
let k = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== nums[k - 1]) {
nums[k] = nums[i];
k++;
}
}
return k;
};
Comments