第四章：如何去除有序数组的重复元素

labuladong 如何去除有序数组的重复元素

用快慢指针解决问题（两种初始化都可以）

slow,fast=0,0
slow,fast=head,head

或者

slow,fast=0,1
slow,fast=head,head.next

26. 删除排序数组中的重复项

• 快指针在前面探路，慢指针在后。快指针在每次前进时，如果和慢指针的元素不同，则慢指针跳1格，然后把快指针的元素赋给慢指针（先跳再赋值）

# nums = [0,0,1,1,1,2,2,3,3,4]
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:return 0
        slow,fast=0,1
        n=len(nums)
        while fast<n:
            if nums[slow]!=nums[fast]:
                slow += 1
                nums[slow]=nums[fast]
            fast+=1
        return slow+1

83. 删除排序链表中的重复元素

与上题一样，也是用快慢指针。最后slow.next=None。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head: return None
        slow=head
        fast=head.next
        while fast!=None:
            if slow.val!=fast.val:
                slow=slow.next
                slow.val=fast.val
            fast=fast.next
        slow.next=None
        return head

27. 移除元素

同样利用快慢指针，若遇到目标值，快指针直接跳过，不进行任何操作。否则将快指针的值赋给慢指针，然后慢指针前进

• 根据对题目的不同要求，与上两题的相比，本题是先给慢指针赋值，慢指针再前进。（先赋值再跳）
  • 如[0,1,0,6],去除0。slow指向0，fast指向0。fast跳到1，此时fast不指向目标值。然后slow处的0被覆盖为1（nums[slow]=nums[fast]），然后slow再向右跳（slow+=1）

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        slow,fast=0,0
        while fast<len(nums):
            if nums[fast]!=val:
                nums[slow]=nums[fast]
                slow+=1
            fast+=1
        return slow

283. 移动零

本题相当于在27题的基础上进行修改：移除所有目标值为0的元素，并把后面的元素赋值为0

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        # 27题去除目标值的代码
        def removeElement(nums, val):
            """
            :type nums: List[int]
            :type val: int
            :rtype: int
            """
            slow, fast = 0, 0
            while fast < len(nums):
                if nums[fast] != val:
                    nums[slow] = nums[fast]
                    slow += 1
                fast += 1
            return slow
        # 去除 nums 中的所有 0，并返回去除0之后的数组长度
        slow=removeElement(nums,0)
        # 然后把slow后面的元素赋值为0
        for i in range(slow,len(nums),1):
            nums[i]=0
        return nums

so=Solution()
nums=[0,1,0,3,12]
print(so.moveZeroes(nums)) # 输出 [1, 3, 12, 0, 0]