26. Remove Duplicate Numbers in Array
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
solution
inplace移除元素类题目,采用同向双指针,慢指针记录有效位置,快指针用来遍历. 类似快速排序中的partition
Missing Number 大类,交换元素,数组环形跳转
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 1 # i: 待更新的位置, 之前都是有效的非重复. 因为已经排过序,且直接重置了重复值,通过和上一个位置比较判断重复
for j in range(1, len(nums)):
if nums[j] != nums[j-1]:
nums[i] = nums[j]
i += 1
return i
时间复杂度:O(n) 空间复杂度:O(n)
follow up
暴力法
# 主要是array本身无法被in-place的修改,因此需要多加一个循环
时间复杂度:O() 空间复杂度:O()
双指针
典型双指针题目,slow记录一个位置
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow = 0 # 待交换的位置
for i in range(len(nums)):
if nums[i] != val:
nums[slow], nums[i] = nums[i], nums[slow]
slow += 1
return slow
时间复杂度:O(n) 空间复杂度:O(1)
80. Remove Duplicates from Sorted Array II
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
for num in nums:
if i < 2 or num != nums[i - 2]: # i标记的是下一个可以交换的位置, 不重复超过两个
nums[i] = num
i += 1
return i
时间复杂度:O(n) 空间复杂度:O(1)
82. Remove Duplicates from Sorted List II
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(-1, next=head)
pre = dummy
while pre.next:
cur = pre.next
while cur.next and cur.val == cur.next.val:
cur = cur.next
if pre.next != cur:
pre.next = cur.next
else:
pre = pre.next
return dummy.next
时间复杂度:O() 空间复杂度:O()
Last updated