题目:
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例:
给定数组 nums=[1,1,2],函数应返回新的长度为2,并且原数组nums的前两个元素被修改为1,2。
思路:
题目已提及了已排序,那么这是一道简单的双指针题。用两个指针指向开始,当数字相同的时候,一个指针向前移动直到数字不同。同时还需要一个变量来保存此刻数组的大小。
我的第一次解法如下:
class Solution { public: int removeDuplicates(vector<int>& nums) { int length=nums.size(); int i=0,j=0; int size=0; for(;i<length&&j<length;) { while(nums[j]==nums[i]&&j<length) j++; size++; nums[size]=nums[j]; i=j; } return size; } };
结果显示还行,证明我的思路和主流解法差不多,来看看大神的解法吧:
static bool init = []() { ios::sync_with_stdio(false); cin.tie(nullptr); return true; }(); class Solution { public: int removeDuplicates(vector<int>& nums) { if(nums.empty()) return 0; int i=0; int j=1; int len =nums.size(); for(;j<len;j++) if(nums[i]!=nums[j]) nums[++i]=nums[j]; return (i+1); } };
几个月不经常用c++看到这个确实有点头晕,看来是acm大佬的写法。用c++11的lambda与与输入绑定的设置,从而加快了cin,cout的执行效率,虽然这里没有关系。再看解答:呀,原来我还忘记了健壮性,当数组为0的时候,直接就返回0。看来也是双指针。