LeetCode Remove Duplicates from Sorted Array II
LeetCode from Array II remove sorted Duplicates
2023-09-11 14:14:59 时间
LeetCode解题之Remove Duplicates from Sorted Array II
原题
在 Remove Duplicates from Sorted Array(从一个有序的数组中去除反复的数字,返回处理后的数组长度) 的基础上。能够使每一个数字最多反复一次,也就是说假设某一个数字的个数大于等于2个,结果中应保留2个该数字。
注意点:
- 仅仅能用常量的额外空间
- 将要保留的数字移到数组前部,剩余的部分不须要处理
样例:
输入: nums = [1,1,1,2,2,3]
输出: 5 ([1,1,2,2,3,3])
解题思路
首先记住原数组是有序的。再看一下下面几种情况:
- [1,1]
- [1,1,2]
- [1,1,2,2]
- [1,1,2,2,3]
在每一次插入过程中,事实上仅仅要把要插入的元素和倒数第二个元素进行比較。假设同样,就忽略,由于倒数第一个数是夹在它们中间的,假设它们相等,那么就会有三个数相等;假设不同,就能够插入。由于在这种情况下。最多仅仅有倒数第二、倒数第一两个数相等。
AC源代码
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = 0
for i in range(len(nums)):
if count < 2 or nums[count - 2] != nums[i]:
nums[count] = nums[i]
count += 1
return count
if __name__ == "__main__":
l = [1, 1, 1, 2, 2, 3]
r = Solution().removeDuplicates(l)
assert l == [1, 1, 2, 2, 3, 3]
assert r == 5
欢迎查看我的Github (https://github.com/gavinfish/LeetCode-Python) 来获得相关源代码。
相关文章
- Leetcode: Campus Bikes II
- Leetcode: Remove Nth Node From End of List
- LeetCode——Remove Duplicates from Sorted List II
- leetcode_Multiply Strings
- JS leetcode 多数元素 题解分析
- [LeetCode] Merge Sorted Array
- [LeetCode] Single Number II
- [LeetCode] Construct Binary Tree from Preorder and Inorder Traversal
- [LeetCode] Remove Duplicates from Sorted Array II
- 【LeetCode】105. Construct Binary Tree from Preorder and Inorder Traversal
- 【LeetCode】106. Construct Binary Tree from Inorder and Postorder Traversal
- 【LeetCode】80. Remove Duplicates from Sorted Array II (2 solutions)
- [LeetCode-20]Construct Binary Tree from Inorder and Postorder Traversal
- LeetCode——Remove Nth Node From End of List
- [LeetCode] 1309. Decrypt String from Alphabet to Integer Mapping 解码字母到整数映射
- [LeetCode] 988. Smallest String Starting From Leaf 从叶结点开始的最小字符串
- [LeetCode] 965. Univalued Binary Tree 单值二叉树
- [LeetCode] Course Schedule III 课程清单之三
- [LeetCode] 581. Shortest Unsorted Continuous Subarray 最短无序连续子数组
- [LeetCode] 19. Remove Nth Node From End of List 移除链表倒数第N个节点
- [LeetCode] 83. Remove Duplicates from Sorted List 移除有序链表中的重复项
- leetcode算法70.爬楼梯