有序集合去重

有序集合去重

今天在 leetcode 它,要求返回唯一元素的个数,并且原地更新当前的集合。


解法

1、如果集合为空就直接返回。

2、设置 fast,slow 两个指针同时指向首元素。

3、fast 一次往前面移动一个元素,每次移动完之后进行检查,当两个元素相等的时候 fast 指定进入下一轮的移动,如果不相等 slow 向前进一个元素,并设置成 fast 所指向元素的值。

4、最终返回 slow + 1 。

public class Solution {
    public int removeDuplicates(int[] nums) {

        // 双指针法的一个前提是数组不为空
        if (nums.length == 0) {
            return 0;
        }

        // 两个指针都从 0 开始
        int slow = 0;
        for(int fast = 0;fast < nums.length;fast ++) {
            if (nums[fast] == nums[slow]) {
                continue;
            }
            else {
                slow = slow + 1;
                nums[slow] = nums[fast];
            }
        }

        // slow + 1 就是去重之后的真实长度
        return slow + 1;
    }
}