首页 > 编程语言 > 详细

4.7 80--删除排序数组中的重复项 II

时间:2021-04-07 20:16:29      阅读:26      评论:0      收藏:0      [点我收藏+]

因为python的list可以直接del List[index],因此直接使用了暴力方法,判断是否重复了两次,是的话直接使用del。

在转向使用Java时,因为暴力方法的局限,一直在找怎样对Java的array进行具体索引的元素删除,但是发现array初始化之后长度并不能进行修改,只能new一个array进行复制,不符合题目原地的要求,转去看题解。

根据题解提示后,采用快慢双指针对原数组进行遍历:

  slow:代表将要返回的数组的后边界(修改后的数组到nums[slow - 1])

  fast: 代表当前遍历到的数字

这题能这么做,是因为原数组是升序,保证了修改后的数组nums[:slow]中一定也是升序。对于当前遍历到的元素,存在着以下的约束关系:

  nums[slow - 2] <=  nums[slow - 1] <=  nums[fast]

因此要判断当前元素nums[fast]是否重复了两次,只需要进行 nums[slow - 2] ?= nums[fast] 的比较:

  if nums[slow - 2] == nums[fast] —— 只要等式成立,那么一定有:

    nums[slow - 2] ==  nums[slow - 1] ==  nums[fast]

  说明当前元素重复了两次,fast可直接跳过:

    fast += 1

  else nums[slow - 2] != nums[fast] —— 要是等式不成立,说明至多只有 nums[slow - 1] ==  nums[fast] 成立,即只有一次重复,还需将元素添加到数组中,数组长度也需+1:

    nums[slow] =  nums[fast]

    slow += 1

    fast += 1

最后返回slow即可。(slow代表了最后数组的长度,修改后的数组是 nums[ : slow])

4.7 80--删除排序数组中的重复项 II

原文:https://www.cnblogs.com/mirror2559/p/14628709.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!