🌕 🌗 80. 删除有序数组中的重复项 II

难度: 🌕 🌗

问题描述

---

解法 1

class Solution {
    public int removeDuplicates(int[] nums) {
        // 思路：
        // 双指针
        int len = nums.length;
        if(len <= 2) {
            return len;
        }
        // len >= 3
        int left = 2;
        int right = left;
        while(left < len && right < len) {
            if((nums[left] == nums[left - 1] && nums[left] == nums[left - 2])
                || nums[left] < nums[left - 1]) {
                // 需要替换 left
                right = Math.max(right, left + 1);
                while(right < len && nums[right] == nums[left]) {
                    right ++;
                }
                if(right == len) {
                    return left; // [left] 节点之前均满足条件 [0, left - 1] == left
                }
                // right < len
                swap(nums, left, right);
                right ++;
            } else {
                left ++;
            }
        }
        if(left == len) {
            return len; // 说明完全没有重复的
        }
        if((nums[left] == nums[left - 1] && nums[left] == nums[left - 2])
                || nums[left] < nums[left - 1]) {
                    return left;
                }
        return left + 1;
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

---

输出 1

---

解法 2 - 优化

class Solution {
    public int removeDuplicates(int[] nums) {
        // 思路：
        // 双指针
        // left 表示左边的已经完全满足，right 表示当前遍历的元素下标
        int len = nums.length;
        if(len <= 2) {
            return len;
        }
        // len > 2
        int left = 2;
        int right = 2;
        while(right < len) {
            if(nums[left - 2] != nums[right]) {
                // [left - 2] 是已经确定要保留的元素，[left - 1] 也是
                // 若 不相等，说明 [right] 可以被保留
                nums[left] = nums[right];
                left ++;
                right ++;
            } else {
                // 与之前保留的元素重复，不保留 [right]，直接 跳过，查看下一个
                right ++;
            }
        }
        return left; // [0, left - 1] 均有效，len = left
    }
}

---

输出