【一天一道Leetcode】删除有序数组的重复项Ⅱ
01
题目描述
题目描述：
给一个有序数组nums，请原地删除重复出现的元素，使每个元素最多出现两次，返回删除后数组的长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。
示例：
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5,
并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
不需要考虑数组中超出新长度后面的元素。提示：
1.0 <= nums.length <= 3*10^4
2.-10^4 <= nums[i] <= 10^4
3.nums 已按升序排列
02
思路和方法
由题意最后只用输出新数组的长度。
我们可以利用遍历，设定两个开始节点。
从数组第一个元素进行遍历，依次对比元素是否相同，将符合题目要求的元素往前移动。
最后输出数组元素不同的那部分长度即可。
例如我们用一个例子来直观地说明。
初始数组num=[1,2,2,2]
设定两个起点进行遍历数组，因为题目要求使每个元素最多出现两次，
所以此时我们设置节点的起始值
node=1,j=2，
num[node]=1，num[j]=2,
如果num[i]!=num[node-1]
通过node++，使得node++的值等于此时i的值。
使得num[node]=num[i]
利用这样的方式，将同一个数组的符合要求的元素都往前移动。
最后输出节点node+1的长度即可。
我们用代码表示为：
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
node = 1
for i in range(2, len(nums)):
if nums[i] != nums[node-1]:
node += 1
nums[node] = nums[i]
return node + 1我们由这道题浮想一下，如果题目继续改为：
给一个有序数组nums，请删除重复出现的元素，使每个元素最多出现n次，返回删除后数组的新长度。
设定n是一个值，我们的函数表达式可以表示为：
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
node = n-1
for i in range(n, len(nums)):
if nums[i] != nums[node-(n-1)]:
node += 1
nums[node] = nums[i]
return node + 1本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-04-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录