2020/10/16删除排序数组中都重复项
2020-10-16 本文已影响0人
小mg
leetCode题目-删除排序数组中都重复项
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
来源：力扣（LeetCode）
代码样式
class Solution {
public int removeDuplicates(int[] nums) {
}
}
我的代码，难得这么强，太激动了！
执行用时：1ms 超过了98.21%
内存消耗：40.1mb 超过了98.72%
class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length==0)return 0;
int cur=nums[0];
int index=1;
for(int i=1;i<nums.length;i++){
if(nums[i]>cur){
nums[index]=nums[i];
index++;
cur=nums[i];
}
}
return index;
}
}
思路
- 首先对题目的分析，返回的是一个整型但输出的是数组。事实上就是需要你在nums的基础上对他进行改造，将重复项去掉，并把改造后的数据从数组下标为0开始的地方依次放入，最后的输出就是根据你返回的整型值来遍历nums数组的前多少项。因此也不用在意数组中，超出你给定长度的元素。
代码分析
- 首先对nums数字是否为空进行判断
- 其次给一个cur和index,cur表示需要比较的下标的数组的值，index表示需要被替换掉的元素的下标。
- 因为nums本身是排好序的，所以nums[0]一定是最小的元素。因此
cur=nums[0]，之后插入的元素也只需要从下标1开始，得出index=1 - 再从下标为1开始遍历数组，只要出现比cur大的值，就将值赋给下标为index的数组，同时index++指向下一个需要改变数组值的位置，之后cur变成当前需要比较的值cur=nums[i]
- 最后返回index,虽然index表示的是下标，而题目需要的是数组的有效长度，但可以发现index一直都是指向当前元素cur的后面一个位置，所以index=数组的有效长度。
官方题解：双指针算法
算法
数组完成排序后，我们可以放置两个指针 iii 和 jjj，其中 iii 是慢指针，而 jjj 是快指针。只要 nums[i]=nums[j]nums[i] = nums[j]nums[i]=nums[j]，我们就增加 jjj 以跳过重复项。
当我们遇到 nums[j]≠nums[i]nums[j] \neq nums[i]nums[j]=nums[i] 时，跳过重复项的运行已经结束，因此我们必须把它（nums[j]nums[j]nums[j]）的值复制到 nums[i+1]nums[i + 1]nums[i+1]。然后递增 iii，接着我们将再次重复相同的过程，直到 jjj 到达数组的末尾为止。
代码
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
思路
和我的想法类似，我是把一个指针直接换成值，官方的效率更高
最后再说一下将图片保存到markdown中
- 需要用到base64图片转码工具
base64图片转码工具 - 最后在md文件中的的格式，因为转码后会有巨多字符，所以需要使用标签
- 标签格式![avatar][dog]
- 文末格式[dog]:data:image/png....;
