发布于 2021-04-12  81 次阅读


醉后不知天在水,满船清梦压星河


  • leetcode80.
    给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 最多出现两次 ,返回删除后数组的新长度。不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
输入:nums = [1,1,1,2,2,3]
输出:5, nums = [1,1,2,2,3]
解释:函数应返回新长度 length = 5,
并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 .
不需要考虑数组中超出新长度后面的元素。
示例 2:
输入:nums = [0,0,1,1,1,1,2,3,3]
输出:7, nums = [0,0,1,1,2,3,3]
解释:函数应返回新长度 length = 7, 
并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。
不需要考虑数组中超出新长度后面的元素。

  • 既然数组是有序的那么问题不就好办了吗,元素必然是连续存放的嘛!
  • 所以我们还是会用到双指针来决定那些元素是应该被保留的
    解法如下

    class solution
    {
    public:
    int removeDuplicates(vector<int>& nums) 
    {
    
        int i{}; //初始化左指针(slow)
    
        if(nums.empty())
        {
            return i;
        }
    
        for(auto num : nums)  //num相当于右指针(fast)
        {
            if(i < 2 || nums[i - 2] != num) //开始判断
            {
                //nums[i++] = num; //slow = fast; slow++;
                nums[i] = num;
                i++;
            }
        }
        return i;
    }
    }

  • leetcode 26 也迎刃而解

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。


示例 1:

输入:nums = [1,1,2]
输出:2, nums = [1,2]
解释:函数应该返回新的长度 2 ,
并且原数组 nums 的前两个元素被修改为 1, 2 。
不需要考虑数组中超出新长度后面的元素。
示例 2:

输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 
并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。
不需要考虑数组中超出新长度后面的元素。

解法如下:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i {};
        if(nums.empty())
        {
            return i;
        }

        for(auto num : nums)
        {
            if(i < 1 || nums[i - 1] != num)
            {
                nums[i++] = num;
            }
        }
        return i;
    }
}

或者


class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k {};  //slow
        if(nums.empty())
        {
            return k;
        }

        for(auto i {1}; i < nums.size(); i++) //遍历整个数组fast
        {
            if(nums[k] != nums[i])
            {
                nums[++k] = nums[i]; // ++slow = fast;
            }
        }
        return ++k;
    }
}

收工


一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。