删除有序数组中的重复项II

发表于
本文字数： 753 阅读时长 ≈ 1 分钟

LeetCode每日一题，80. Remove Duplicates from Sorted Array II

先看题目描述

c1SK3t.png

算法和思路

双指针

这题可以使用两个指针 i 和 j，其中 i 是慢指针，j 是快指针。慢指针表示处理出的数组长度，快指针表示已检查过的数组长度

由于题目要求相同元素最多重复两次，因此将 nums[j] 与 nums[i - 2] 进行比较

  • 若 nums[j] 与 nums[i - 2] 相等，那么说明 nums[i - 2] == nums[i - 1] == nums[j]，出现三个重复元素，将 j 跳过，j++
  • 否则，说明 nums[j] 可以被保留，令nums[i] = nums[j]，j++，i++

最后 i 的值就是处理后的数组长度

算法源码

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len <= 2) {
            return len;
        }
        int i = 2;
        for (int j = 2; j < len; j++) {
            if (nums[i - 2] != nums[j]) {
                nums[i] = nums[j];
                i++;
            }
        }
        return i;
    }
}