26. 删除排序数组中的重复项
两种方法的比较:
第一种方法,是前后两个元素是否相等,如果不等,将其存储到k所指示的地址中去,
第二种方法,是比较数组中其他位置的元素是否跟当前k所指示的元素是否相等,如果不等,k + 1,存储新元素,否则,i + 1 ,继续判断
方法二的效率更高一些
第一种方法
如果数组元素个数大于0,那么必然至少有一个数字,所以设变量k=1,指示有多少个不重复的元素个数,只要 nums[i] == nums[i-1],我们增加i的值以跳过重复项,当我们遇到 只要nums[i] != nums[i-1] 的时候,重复运动已经结束,我们必须把nums[i] 复制到 nums[k],然后递增i,再次重复相同的过程,知道i达到数组的末尾
int removeDuplicates(int* nums, int numsSize) {
if (numsSize == 0) return 0;
int k = 1;
for (int i = 1; i < numsSize; i++) {
if (nums[i] == nums[i-1]) continue;
nums[k++] = nums[i];
}
return k;
}
第二种方法
k是慢指针,i是快指针,只要nums[k] == nums[i] 我们增加i的值以跳过重复项,当我们遇到 只要nums[k] != nums[i] 的时候,重复运动已经结束,我们必须把 nums[i] 复制到 nums[k + 1],然后递增i,再次重复相同的过程,知道i达到数组的末尾
int removeDuplicates(int* nums, int numsSize) {
if (numsSize == 0) return 0;
int k = 0;
for (int i = 1; i < numsSize; i++) {
if (nums[i] != nums[k]) {
k++;
nums[k] = nums[i];
}
}
return k + 1;
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
int a[] = {0,0,1,1,1,2,2,3,3,4};
int b = removeDuplicates(a, sizeof(a)/sizeof(int));
printf("一共有多少不重复的元素个数%d\n",b);
}
return 0;
}
网友评论