编写一个程序，删除有序数组中的重复元素。要求时间复杂度为O(n)，空间复杂度为O(1)
例如：
输入
[1,1,2,3,3,3,4]
或
[2,5,5,7,7,9,9]
输出
[1,2,3,4]
或
[2,5,7,9]
思考： 首先令a = nums[0])(第一个元素),然后从第二个元素(i=1)开始依次往后检查是否与a相等，如果相等，就继续后移(i++)，直到nums[i]与a不等，就将新的数字nums[i]加到“不重复数组”的最后面，因此，需要一个指示器end用于指示“不重复数组”的后面位置，初始时end = 1 (因为只有一个元素a= nums[0])。
一旦将新的不重复数字nums[i]加到“不重复数组”里，就设置a=nums[i]为这个新的数字，再去检查i后面的是否是与之相同，…
算法运行过程如下所示：
a = nums[0]; //初始化第一个不重复数字
end =1; //说明已经发现1个不重复元素在nums[0]里
i = 1
[1, 1, 2, 3, 3, 3, 4]
end = 1
i = 2
[1, 1, 2, 3, 3, 3, 4]
end = 1
此时 nums[i]!=a;需要将nums[i]作为一个新发现的不重复数,执行：
nums[end] = nums[i];
a = nums[i];
end++; i++;
结果已经得到了2个不重复元素[1,2]：
i = 3
[1, 2, 2, 3, 3, 3, 4]
end = 2
解答：
int removeDuplicates(int[] nums,int n) {
if(n == 0) return 0;
int a = nums[0];
int end = 1;
for(int i = 1; i < n; i++){
if(nums[i]!=a){
nums[end] = nums[i];
a = nums[i];
end++;
}
}
return end;
}
赏
支付宝打赏
微信打赏
支付宝打赏
微信打赏
您的打赏是对我最大的鼓励！
