算法 1.7 双指针：删除排序数组的重复项【leetcode 2
题目描述
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
给定数组 nums = [1, 1, 2];
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2
你不需要考虑数组中超出新长度后面的元素。
给定数组 nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4
你不需要考虑数组中超出新长度后面的元素。
说明：为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
数据结构
- 指针
算法思维
- 双指针、遍历
解题要点
- 什么情况下要想到使用双指针解决问题？
1.按照一定规律 同步变化 并 相互影响 的两个数据
2.范围问题
解题步骤
一. Comprehend 理解题意
1. 题目主干要求
删除重复出现的元素，使每个元素只出现一次
返回移除后数组的新长度
2. 附加限制要求
原地删除重复出现的元素
不使用额外数组空间，额外空间复杂度O(1)
3. 宽松条件
给定一个排序数组
重复元素都是相邻的
不需要考虑数组中超出新长度后的元素
4. 其它细节
给定数组可能为空的情况
数组下标问题，在编写代码时要注意边界问题
元素重复次数没有限定，可能是0到n-1次（n为数组长度）
二. Choose 选择数据结构与算法
数据结构选择
- 题目限定了额外O(1)的空间
- 给定的数组
算法思维选择
- 遍历
- 比较
三. Code 编码实现基本解法
解法一：暴力解法思路分析
- 遍历数组
- 依次比较相邻的元素（i和i+1）
不同：向后遍历，i++；
相同：后面所有元素前移一位； - 每遇到重复元素，数组长度缩减1
边界问题
- 数组索引越界
- 循环退出条件：遍历到 length – 1 时
细节问题
- 每次处理重复数据后，需要 i 与 i+1 再比较一次，避免掉落元素
- 相邻元素不相等时，索引才能继续指向下个元素
class Solution {
public int removeDuplicates(int[] nums) {
int length = nums.length; // 数组长度
// 1.遍历数组
for(int i = 0; i < length - 1;) {
// 2.依次比较相邻的元素
if(nums[i] != nums[i + 1]) {
// 2.1.不同：向后遍历
i++;
}
else {
// 2.2.相同：后面所有元素前移一位
for(int j = i + 1; j < length - 1; j++) {
nums[j] = nums[j + 1];
}
// 3.每遇到重复元素，数组长度缩减1
length--;
}
}
return length;
}
}
时间复杂度：O(n2) -- 循环遍历进行比较 O(n)，每遇到重复元素都要前移后续元素 O(n)
空间复杂度：O(1) -- 临时变量 O(1)
执行耗时：177 ms，击败了 5.06% 的Java用户
内存消耗：40.4 MB，击败了 88.26% 的Java用户
四. Consider 思考更优解
剔除无效代码，优化空间消耗
- 前移后续所有元素的操作是必须的吗？
寻找更好的算法思维
- 待移动元素能否一次性移动到目标位？
- 双指针：分别记录待移动元素和目标位置的索引
- 参考其它算法
五. Code 编码实现最优解
最优解：双指针解法
- 定义两个指针（索引）分别指向目标位和待移动元素位
初始目标位为0，待移动元素位为1 - 比较两个指针对应的数据
比较相等：目标位不变，待移动位加1
比较不等：目标位加1，待移动元素赋值到目标位；待移动位加1
边界问题
- 只需要一层循环，循环退出条件：待移动指针超出数组范围
细节问题
- 题目要求返回数组新长度，即目标位对应的数据是最后一个元素，下标+1
- 尝试移动元素前，若目标位与待移动位相同，跳过赋值操作
class Solution {
public int removeDuplicates(int[] nums) {
// 1.定义两个指针（索引）分别指向目标位和待移动元素位
int target = 0; // 目标位指针
for(int i = 1; i < nums.length; i++) { // i为待移动位指针
// 2.比较两个指针对应的数据
if(nums[target] != nums[i]) {
// 不相等，则把目标位置后移
if(++target != i) {
nums[target] = nums[i];
}
}
}
return target + 1;
}
}
时间复杂度：O(n) -- 一次循环遍历 O(n)
空间复杂度：O(1) -- 两个指针变量 O(1)
执行耗时：1 ms，击败了 97.67% 的Java用户
内存消耗：39.9 MB，击败了 99.29% 的Java用户
六. Change 变形与延伸
延伸扩展
- 什么情况下使用双指针：两个按照一定规律同步变化且相互影响的数据；范围问题
- 合理的使用双指针能将时间复杂度从O(n2)降低到O(n)
