zroger's blog

LeetCode 笔记

ZRoger ZRoger #LeetCode

LeetCode 随心记录

一个地方记录 LeetCode

从排序数组中删除重复项

ZRoger ZRoger #Array#算法#LeetCode

LeetCode 26 题的双指针解法：用快慢指针原地去重有序数组，附逐步推演表格与 Java 实现。

题目地址

题目地址：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

最终结果

代码实现

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 ;
    }
}