LeetCode 关于 「删除有序数组重复项」的通解

LeetCode 关于 「删除有序数组重复项」的通解

本文的背景来自于解决 LeetCode 26[1]、LeetCode 80[2] 两个题目

其实社区已经有比较好的解题思路了，比如 【宫水三叶】关于「删除有序数组重复项」的通解[3]。

我个人觉得蛮好的，但是此篇还是记录自己的理解和学习～

拿第 26 题来做个讲解：

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过： 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。 返回 k 。

function removeDuplicates(nums: number[]): number {
    const n = nums.length;
    if(n <= 1)  return n;
    let slow = 1, fast = 1;
    while(fast < n) {
        if(nums[slow-1]!==nums[fast]) {
            nums[slow] = nums[fast];
            ++slow;
        }
        ++ fast;
    }
    return slow;
};

核心思想是：双指针，定义快慢指针，快指针用来“扫栈”，慢指针用来“标记唯一元素”。

所以，顾名思义，慢指针不一定等于快指针，因为会去重。

比如一组输入为：[0,1,1,2,3,3]

同比，咱们根据“规律法”做通解方法：

function commonResolver(k: number)  {
    return function removeDuplicates(nums: number[]): number {
               const n = nums.length;
               if(n <= k)  return n;
               let slow = k, fast = k;
               while(fast < n) {
                   if(nums[slow-k]!==nums[fast]) {
                       nums[slow] = nums[fast];
                       ++slow;
                   }
                   ++ fast;
               }
               return slow;
           };
}

0.16%的用户使用了此解法～

引用链接

[1] LeetCode 26: https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150 [2] LeetCode 80: https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/?envType=study-plan-v2&envId=top-interview-150 [3] 【宫水三叶】关于「删除有序数组重复项」的通解: https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/solutions/1/gong-shui-san-xie-guan-yu-shan-chu-you-x-glnq/?envType=study-plan-v2&envId=top-interview-150