从排序数组中删除重复项

题目地址

题目地址: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
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int removeDuplicates(int[] nums) {
int length = nums.length ;
int lowPoint = 0 ;
for(int fastPoint = 0 ; fastPoint < length ; fastPoint++){
if(nums[fastPoint] != nums[lowPoint] ){
lowPoint ++ ;
nums[lowPoint] = nums[fastPoint];
}
}
return lowPoint + 1 ;
}
}
- the End -
0%