美文网首页
leetcode 初级之数组篇 01

leetcode 初级之数组篇 01

作者: ngugg | 来源:发表于2018-09-12 23:17 被阅读4次

    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;
    }
    

    相关文章

      网友评论

          本文标题:leetcode 初级之数组篇 01

          本文链接:https://www.haomeiwen.com/subject/sakigftx.html