题目地址
题目地址:https://leetcode.com/problems/remove-duplicates-from-sorted-array/
思路
- 数组下标
- 快慢指针
使用快慢指针来记录遍历的坐标。
- 开始时这两个指针都指向第一个数字
- 如果两个指针指的数字相同,则快指针向前走一步
- 如果不同,则两个指针都向前走一步(之后将慢指针所在的节点值换成快指针所指位置)
- 当快指针走完整个数组后,慢指针当前的坐标加1就是数组中不同数字的个数
草稿模拟
数组下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
数组 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 4 |
快指针 | 0 | |||||||||
慢指针 | 0 |
初始时
数组下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
数组 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 4 |
快指针 | 1 | |||||||||
慢指针 | 0 |
两个指针指的数字相同,则快指针向前走一步
数组下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
数组 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 4 |
快指针 | 2 | |||||||||
慢指针 | 0 |
当2个指针对应的值不相同时
数组下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
数组 | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 4 |
快指针 | 2 | |||||||||
慢指针 | 1 |
慢指针前进一步,将当前的值换成快指针所在值
接下来的步骤就是如上这般,最终的结果:
数组下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
数组 | 0 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 3 | 4 |
快指针 | 9 | |||||||||
慢指针 | 4 |
最终结果
代码实现
1 | class Solution { |