# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://longxingtan.gitbook.io/mle-interview/01_leetcode/01_two_pointers/26.-remove-duplicate-numbers-in-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.