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
加油!:)
00
相似问题