博客主页：https://tomcat.blog.csdn.net
博主昵称：农民工老王
主要领域：Java、Linux、K8S
期待大家的关注💖点赞👍收藏?留言💬
创作申明
本文是一篇针对leetcode算法题的解题博客。我给出的解题思路和代码，以及对优质解答的讲解 均属于原创内容，本文的原创标识也是基于此。而题目全部出自leetcode.cn，优质解答搜索自全网，本文已经标明其引用出处。我是一个算法初学者，完全的菜鸟，文中的算法题属于入门级别。本文适合算法新手阅读，而对算法大佬没有任何阅读价值。
题目
题目链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2gy9m/
题干
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 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 。不需要考虑数组中超出新长度后面的元素。
题目分析
这个题的难点是“原地”，也就是说不能再新建一个数组。
我的解答
本题用Java实现。
我在审题时就出问题了，忽略了字符串是有序的这一重要信息。在这个情况下，我开始了自己的解答，我的计划是将整个目标分为两步走，先实现去重，再实现元素的顺序保持一致。
第一步，实现去重，我的思路是双重遍历如果发现重复的，就用最后一位有效元素覆盖重复元素，然后最后一位有效元素就用0覆盖。
public int removeDuplicates(int[] nums) {
int del = 0;
int oldLength = nums.length;
for (int i = 0; i < oldLength - 1; i++) {
for (int j = i + 1; j < oldLength - del; j++) {
if (nums[i] == nums[j]) {
nums[i] = nums[oldLength - 1 - del];
nums[oldLength - 1 - del] = 0;
del++;
}
}
}
return oldLength - del;
}
用下面的测试代码检测，证明能实现既定目标。
@Test
public void test(){
int[] ints = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
int result = removeDuplicates(ints);
System.out.println("返回值：" + result);
System.out.println("-------------");
System.out.print("结果：");
for (int i = 0; i < result; i++) {
System.out.print(ints[i] + " ");
}
System.out.println("");
}
第二步，在元素的顺序保持一致前提下实现去重，我的思路是双重遍历，如果发现重复的，把后面的元素全部前移一位，就直接覆盖了那个重复元素。但是在这种情况下，内层遍历的数组索引不应该增加，因为当前索引的重复元素已经被覆盖，现在是一个新的元素，所以应该继续判断当前索引。而如果发现当前索引的元素不是重复元素，才应该向后移动索引。所以内层最好是用while循环。
public int removeDuplicates(int[] nums) {
int del = 0;
int oldLength = nums.length;
for (int i = 0; i < oldLength - del- 1; i++) {
int j = i + 1;
// 此处一定注意减去del,否则会导致死循环
while (j < oldLength-del) {
if (nums[i] == nums[j]) {
for (int k = j; k < oldLength - del -1; k++) {
nums[k] = nums[k + 1];
}
nums[oldLength - 1] = 0;
del++;
}else {
j++;
}
}
}
return oldLength - del;
}
用上面的测试代码检测，发现完成了题目要求的目标。
提交到leetcode后也是通过了的，只是说时间复杂度上太高。
优质解答
leetcode网页中，题目下面的第一条讨论（作者力扣id：数据结构和算法）中提到的答案就非常优质，获得了很多人的点赞和认同。
直到看到了这位大佬的解析，我才发现数组升序是非常重要的参考因素。不过在我知道这个信息后，我也尝试了自己独立思考，找出相对于上面的解答更高效的解答，但还是没有思绪。然后我就认真阅读了这位大佬的答案。
他的关键词是双指针，实质上是用两个指针把数组中不重复的元素移动到数组最前面，的确非常高效，时间复杂度只有O(n)。
右指针的作用是扫描整个数组，所以无论任何情况它都要向右移动，所以将右指针写在了for循环的条件里。左指针的初始值是0，右指针的初始值是1，这样才可以开始比较。如果左指针和右指针指向的值一样，说明右指针上面的是重复值，就可以直接跳过，体现在代码上，就是，不做任何操作不处理，不过右指针还是会在for循环的运行下向右移。如果两个指针对应的值不一样，就说明右指针上的值需要被记录，这时候需要先把左指针加1，这样左指针就指向了一个新的位置，就可以存放右指针的值。
总之，就是右指针扫描，左指针存值。
public int removeDuplicates(int[] A) {
//边界条件判断
if (A == null || A.length == 0)
return 0;
int left = 0;
for (int right = 1; right < A.length; right++)
if (A[left] != A[right]){
A[++left] = A[right];
}
return ++left;
}
提交这位大佬的代码，其结果秒杀我上面的时间复杂度。不过我的内存消耗比他少。哈哈。
另外还有一点，就是我的代码兼容任何升序、降序、无序的数组，而这个参考答案仅仅使用于当前题目中的有序数组。如果用{0, 0, 1, 0, 1, 2, 2, 3, 3, 4}这个数组来测试，这个参考答案就不能实现去重，如图所示。
不过这也不在题目要求内。
总之和这个参考答案相比，我的解答就像一坨屎。此刻我只想对自己说：“老王，这就是差距啊，你要知耻啊！”
如需转载，请注明本文的出处：农民工老王的CSDN博客https://blog.csdn.net/monarch91 。
