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

27. Remove Element

• 暴力法

# 主要是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()

283. Move Zeroes