怒刷力扣(删除有序数组中的重复项)

2022-06-01 180

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 给你一个升序排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。

删除有序数组中的重复项

WangScaler: 一个用心创作的作者。
声明：才疏学浅，如有错误，恳请指正。

题目

给你一个升序排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

分析

初步思考

这个题的目的就是把数组中重复的元素删除。为了避免数组的移动，我们可以创建一个新的数组来存放我们去重的元素。但是在java中，一是创建数组要先分配大小、而是题目要求我们不要使用额外的空间，你必须在原地修改输入数组。那么第一种方法是不可行的，其次数组是有下标的，也就意味着删除元素，那么后边的所有元素就需要往前移动，才能满足我们的目的。

继续思考

那么这个题的核心就是我们要怎么避免全部移动而且还能实现我们的目标了。

值得注意的是，题目要求我们只需要保证前k个条件符合要求就行。那么我们只需要保证数组的前k个元素就可以了，无需管k+1之后的元素，也就是说我们并不需要全部移动后边的元素。遍历完后边的值是什么我们无需考虑，我们只需要把新的元素从原有重复的元素替换出去就可以了。

首先我们遍历数组，用两个指针分别标记我们遍历完的位置（即我们已经处理完毕的数组的最后一个位置）和遍历的位置的指针。

如果遍历的元素和第一个指针指向的元素的前一个不一样，那么把新的值赋予给目标值且把两个指针都后移。如果一样，前一个指针不动，后一个指针一直遍历到元素不一样为止。

答案

public static int removeDuplicates(int[] nums) {
        int target = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[target - 1]) {
                nums[target] = nums[i];
                target += 1;
            }
        }
        return target;
    }

遍历完target就是数组去重之后的元素个数。nums的前target个元素就是我们去重之后的结果。