企业官网建设流程全解析

题目概览

给你一个非严格递增排列的数组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^4
• -100 <= nums[i] <= 100
• nums已按非递减顺序排列。

来源：26. 删除有序数组中的重复项 - 力扣（LeetCode）

解题分析

方法：三指针

定义三个指针 i，j，k 分别指向 头、头+1、头，那么：

1. 当 nums[ i ] == nums[ j ] 时，有重复元素，不断移动 j 即 j++ 直到不相等，然后将 nums[ k ] 设置为 nums[ i ]，最后 i 移动到 j 的位置，j 和 k 往后移动一位，继续重复操作
2. 当 nums[ i ] != nums[ j ] 时，没有重复元素，将 nums[ k ] 设置为 nums[ i ]，所有指针往后移动一位即可
3. 当 k >= n 时，遍历完成，返回 k

时间复杂度：O(n)
空间复杂度：O(1)

class Solution { public int removeDuplicates(int[] nums) { int n = nums.length, i = 0, j = 1, k = 0; if (n == 0) { return 0; } while(i < n && k < n) { nums[k++] = nums[i]; while (j < n && nums[i] == nums[j]) { j++; } i = j++; } return k; } }