Skip to content

Latest commit

 

History

History
82 lines (70 loc) · 2.77 KB

26.删除有序数组中的重复项.md

File metadata and controls

82 lines (70 loc) · 2.77 KB
// 复习
// 数组遍历O(1)复杂度原地tp覆盖问题:
1)swap前后交换。
2)slow、fast快慢双指针,后面直接覆盖前面,会造成一些值丢失,但无所谓。
3)tmp临时记录。

输入
nums = [0,0,1,1,1,2,2,3,3,4]
预期结果
[0,1,2,3,4]

int removeDuplicates(vector<int>& nums) {
    int slow = 0;
    int cur = 0;
    for (int fast = 0; fast < nums.size(); fast++) {
        if (slow == 0) {
            nums[slow] = nums[0];
            cur = nums[slow];
            slow++;
        }
        if (nums[fast] > cur) {
            nums[slow] = nums[fast];
            cur = nums[slow];
            slow++;
        }
    }
    return slow;
}

我的错误思路
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 1) return 1;
        int i = 1, k = 0;
        while (i < nums.size()) {
            while (i < nums.size() && nums[i - 1] == nums[i]) {i++;}
            nums[k] = nums[i - 1];
            i++;
            if (!(i >= nums.size() && nums[i-1] == nums[i-2])) k++;
        }
        if (nums[i-1] != nums[i-2]) nums[k] = nums[i - 1];
        return k + 1;
    }
};


举例:[1,1,2,2,3] [1,1,2,2,3,3]
核心:快慢双指针,fast用来定位下一个不一样的数,slow用来定位新的不重复数组下标。

思维误区1:因为第0数始终不会删,从第1个开始删除,所以fast和slow都从1开始,而我上面的解答为了从0开始,就取nums[k] = nums[i - 1],
陷入误区,导致后面容易越界,所以要多思考简单直接的方法nums[slow] = nums[fast],特殊的(比如从1开始)就特殊处理。

思维误区2:我上面的解答用了2while,一看就不合理。“一般快慢双指针,就是1while快的fast一直走,慢的slow看条件走,就比较合理,应该形成框架意识形态”。
这样边界条件fast>=n时就很直观简单,不需要过多考虑。因为fast的值在他第一次触及到(比如最后的3)时就已经赋过了。


所以此题的正确反推思路:先定快慢双指针框架,1个while1个快走1个慢走,然后nums[slow] = nums[fast]要确定,就会定nums[fast] != nums[fast - 1],
为了不越界,一般都是i-1和i的形式,然后就会发现第0个数没给到slow,然后单独处理第0个数(此题刚好第0个数不需要处理)

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1; // wyh 都从1开始
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast; // wyh fast放在while最后++
        }
        return slow;
    }
};