【JAVA】力扣-26-删除有序数组中的重复项_力扣有一个长度为n的数组array,清除重复数字

一、问题

力扣题目链接：删除有序数组中的重复项

提示：

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 升序 排列

二、解题思路

由于数组已经排序，所以重复的元素一定连在一起，但如果毎找到一个重复元素就立即原地删除它，由于数组中删除元素涉及数据搬移，整个时间复杂度是会达到 O(N^2)。

高效解决这道题就要用到快慢指针技巧：

我们让慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。

这样，就保证了 nums[0…slow] 都是无重复的元素，当 fast 指针遍历完整个数组 nums 后，nums[0…slow] 就是整个数组去重之后的结果。

三、解题代码

int removeDuplicates(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    int slow = 0, fast = 0;
    while (fast < nums.length) {
        if (nums[fast] != nums[slow]) {
            slow++;
            // 维护 nums[0..slow] 无重复
            nums[slow] = nums[fast];
        }
        fast++;
    }
    // 数组长度 + 1
    return slow + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16