26. 删除有序数组中的重复项
题目描述
输入一个已按非递减顺序排好的整数数组 nums。设其中不同的值共有 k 个。
直接在 nums 上修改：让前 k 个位置依次放着这 k 个不同的值，每个值只出现一次，顺序与它们在原数组中的顺序一致。下标 k 及之后放什么都可以。
函数返回 k。判题时会检查返回值，并逐个核对 nums 的前 k 个元素。
本页示例输出写成 [k, nums 的前 k 个元素] 的形式。
示例 1
输入：nums = [1,1,2] 输出：[2,[1,2]]
解释：不同的值有 1 和 2 两个，返回 2，nums 前两位是 [1,2]。
示例 2
输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：[5,[0,1,2,3,4]]
解释：不同的值有 5 个，返回 5，nums 前五位是 [0,1,2,3,4]。
数据范围
1 <= nums.length <= 3 * 10^4-100 <= nums[i] <= 100nums已按非递减顺序排好。
解题思路
k 表示已经写好的去重前缀长度。顺序扫描每个 x：如果前缀为空，或 x 与前缀最后一个数 nums[k-1] 不同，x 就是新值，写到 nums[k] 并让 k 加 1；否则 x 是重复值，直接跳过。
为什么正确
每处理完一个元素，nums[:k] 恰好是已扫描部分的所有不同值，按原顺序排列。
复杂度分析
时间 O(n)，额外空间 O(1)。
易错点
要和前缀最后一个数 nums[k-1] 比较，不要和原数组的前一个数 nums[i-1] 比较。前面的位置可能已经被改写。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
k = 0
for x in nums:
if k == 0 or nums[k - 1] != x:
nums[k] = x; k += 1
return kclass Solution {
public int removeDuplicates(int[] nums) {
int k = 0;
for (int x : nums) {
if (k == 0 || nums[k - 1] != x) {
nums[k] = x; k++;
}
}
return k;
}
}class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int k = 0;
for (int x : nums) {
if (k == 0 || nums[k - 1] != x) {
nums[k] = x; k++;
}
}
return k;
}
};func removeDuplicates(nums []int) int {
k := 0
for _, x := range nums {
if k == 0 || nums[k-1] != x {
nums[k] = x
k++
}
}
return k
}var removeDuplicates = function(nums) {
let k = 0;
for (const x of nums) {
if (k === 0 || nums[k - 1] !== x) {
nums[k] = x; k++;
}
}
return k;
};function removeDuplicates(nums: number[]): number {
let k = 0;
for (const x of nums) {
if (k === 0 || nums[k - 1] !== x) {
nums[k] = x; k++;
}
}
return k;
}