> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/01_two_pointers/26.-remove-duplicate-numbers-in-array.md).

# 26. Remove Duplicate Numbers in Array

<https://leetcode.com/problems/remove-duplicates-from-sorted-array/>

## solution

* inplace移除元素类题目，采用同向双指针，慢指针记录有效位置，快指针用来遍历. 类似快速排序中的partition
* Missing Number 大类，交换元素，数组环形跳转

```python
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](https://leetcode.com/problems/remove-element/)

* 暴力法

```python
# 主要是array本身无法被in-place的修改，因此需要多加一个循环

```

时间复杂度：O()\
空间复杂度：O()

* 双指针
  * 典型双指针题目，slow记录一个位置

```python
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](https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/)

```python
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](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)

```python
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](/mle-interview/01_leetcode/01_two_pointers/283.-move-zeroes.md)