leetcode第80题:删除有序数组中的重复项II ,思路感觉没问题,但运行不通过。

来源:3-3 在LeetCode上解决第一个问题 Move Zeros

学者吴与伦

2018-08-19

我的思路是这样的:声明一个int 型变量 k,在[0,k]范围内保存遍历后合格的元素,合格的判定方法有两个判断,一个是遍历时与k对应的元素不相等的元素。第二个判定是处理每个元素最多出现两次,我是当遍历到 i 个元素时,判断 i 对应的元素与上一个元素相等,与上上个元素,也就是 i - 2 对应的元素不相等。具体实现代码如下:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size < 3){
            return nums.size;
        }
        int k = 1;
        for(int i = 2; i < nums.size(); i++){
            
            if(nums[i] != nums[k] || (nums[i] == nums[i - 1] && nums[i] != nums[i - 2])){
                k++;
                nums[k] = nums[i];
            }
        }
        return k + 1;
    }
};

i 从 2开始遍历是为了i 要与 i - 2进行元素大小的比较,为了防止出现数组越界的问题。k 赋初值为 1 是新数组的前两个元素肯定为数组的前两个元素,遍历时如果元素合格,k + 1后 与 i 对应的元素交换位置。 然后 执行代码,输入[1,1,1,2,2,3]
,却输出[1,1,2,3],这我就感到有点费解了,bobo老师,我表达的清不清楚?希望指点一下。

写回答

1回答

liuyubobobo

2018-08-19

这么小的测试用例,稳定的出现错误。实际跟一遍,看看你的逻辑,在输入[1,1,1,2,2,3],为什么2只输出了一次?


如果需要,可以参考我的代码:https://github.com/liuyubobobo/Play-Leetcode/blob/master/0080-Remove-Duplicates-from-Sorted-Array-II/cpp-0080/main.cpp


加油!:)

0
0

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程