本文主要是介绍leetcode算法-删除排序数组中的重复项 II-80，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
leetcode算法-删除排序数组中的重复项 II
leetcode传送门
题目
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定 nums = [1,1,1,2,2,3],
函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,1,2,3,3],
函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。
你不需要考虑数组中超出新长度后面的元素。
解题思路
本题要求写的是一个原地算法,不能够创建新数组。
这位作者使用的是双指针法,一个指针代表原数组当前元素的索引,一个指针代表新数组已经赋值的元素的长度或者下一个将要赋值的元素的索引。然后遍历原数组,当新数组指针小于2的时候，可以直接将nums[i]赋值给新数组元素,因为新数组指针小于2的时候是必定不会出现每个元素出现超过2次的情况的,当原数组当前遍历元素n大于新数组倒数第二个元素时,此时便达成了每个元素最多连续出现两次的约束,是此算法最为精妙的地方。之后新数组指针后移。重复上述步骤,最后返回新数组指针i即可。
代码
class Solution {public int removeDuplicates2(int[] nums) {int i = 0;for (int n : nums)if (i < 2 || n > nums[i-2])nums[i++] = n;return i;}
}
PS:此代码出自leetcode
这篇关于leetcode算法-删除排序数组中的重复项 II-80的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
