026_从排序数组中删除重复项

风扫地

1. /*
   
2. 给定一个[排序数组]，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
   
3. 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成.
   
4. 示例 1:
   
5. 给定数组 nums = [1,1,2],
   
6. 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
   
7. 你不需要考虑数组中超出新长度后面的元素。
   
8. 示例 2:
   
9. 给定 nums = [0,0,1,1,1,2,2,3,3,4],
   
10. 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
    
11. 你不需要考虑数组中超出新长度后面的元素。
    
12. 说明:
    
13. 为什么返回数值是整数，但输出的答案是数组呢?
    
14. 请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
    
15. 你可以想象内部操作如下:
    
16. // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
    
17. int len = removeDuplicates(nums);
    
18. // 在函数里修改输入数组对于调用者是可见的。
    
19. // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
    
20. for (int i = 0; i < len; i++) {
    
21.     print(nums[i]);
    
22. }
    
23. */

复制代码

解法。

1. /*
   
2. 基本思想:
   
3. 把数组分为两个部分:
   
4. 第一部分:已经没有重复项的部分(由num[0]开始)
   
5. 第二部分:可能还有重复性的部分
   
6. 逐一"消灭"第二部分的元素.
   
7. "挤压队列"
   
8. */
   
9. 
   
10. #include <stdio.h>
    
11. 
    
12. int removeDuplicates(int* nums, int numsSize)
    
13. {
    
14.     int  len            = 0;
    
15.     int  inner_count    = 0;
    
16.     int  i              = 0;
    
17.     do{
    
18.         /* 输入参数检查,能直接处理的直接处理*/
    
19.         if(  (nums == NULL)
    
20.         ||(numsSize <= 0)
    
21.         )
    
22.         {
    
23.             len = 0;
    
24.             break;
    
25.         }
    
26.         if(numsSize==1)
    
27.         {
    
28.             len = 1;
    
29.             break;
    
30.         }
    
31. 
    
32.         len           = 1;/* 已经保证数组长度至少为2,len既是长度计数,也指向未进入无重复项区域的元素 */
    
33.         inner_count   = 1;/* 标记已经处理过的原始数组的数据个数                                     */
    
34.         while(1)
    
35.         {
    
36.             if(nums[len-1]==nums[len]) /* 本来要遍历0~len-1,但已经确认是"排序数组",只需要比较前一个就可用了*/
    
37.             {
    
38.                
    
39.                 // 已经索引到原始数组的 已经处理掉count个,覆盖一个相当于尾巴去掉一个,所以 i = [0,numsSize - inner_count - 1)
    
40.                 for( i = 0; i < numsSize - inner_count - 1 ; i++ )    /*挪动可能还有重复数的部分,使得(nums+len)指向下一个要判断的元素*/
    
41.                 {
    
42.                     nums[len+i] = nums[len+i+1];   
    
43.                 }
    
44.             }
    
45.             else
    
46.             {
    
47.                 len++;  /* 纳入已经没有重复项的部分 */
    
48.             }
    
49.                
    
50.             inner_count++;  /* */
    
51.             if(inner_count > numsSize - 1)
    
52.             {
    
53.                 break;
    
54.             }
    
55.         };
    
56.         
    
57.         break;
    
58.     }while(0);
    
59.     return len;
    
60. }
    
61. 
    
62. 
    

复制代码

测试代码

1. int main(void)
   
2. {
   
3.     int nums[5] = {112,112,113,114,115};
   
4.    
   
5.     int len = removeDuplicates(nums,4);  // 那么这样，arr[3] 和 arr[4] 应该可用保持不变(只读不写)
   
6.    
   
7.    
   
8.     for(int i = 0;i<5;i++)
   
9.     {
   
10.         printf("%d\n",nums[i]);
    
11.     }
    
12.     return 0;
    
13. }

复制代码

1. /*
   
2. 161 / 161 个通过测试用例
   
3. 状态：通过
   
4. 执行用时 : 504 ms, 在Remove Duplicates from Sorted Array的C提交中击败了9.31% 的用户
   
5. 内存消耗 : 9.8 MB, 在Remove Duplicates from Sorted Array的C提交中击败了74.91% 的用户
   
6. 执行耗时爆表了.
   
7. */

复制代码

风扫地

时间效率差远了~还得想想办法。

jackz007

      楼主看看这个代码如何

1. #include <stdio.h>
   
2. 
   
3. int removeDuplicates(int * nums , int numsSize)
   
4. {
   
5.         int d , i , k                                   ;
   
6.         bool f                                          ;
   
7.         d = 0                                           ;
   
8.         if(nums != NULL && numsSize > 0) {
   
9.                 for(d = 1 , i = 1 ; i < numsSize ; i ++) {
   
10.                         for(f = false , k = 0 ; k < d ; k ++) {
    
11.                                 if(nums[k] == nums[i]) {
    
12.                                         f = true        ;
    
13.                                         break           ;
    
14.                                 }
    
15.                         }
    
16.                         if(! f) nums[d ++] = nums[i]    ;
    
17.                 }               
    
18.         }
    
19.         return d                                        ;
    
20. }
    
21. 
    
22. int main(void)
    
23. {
    
24.         int b[] = {0 , 1 , 1 , 1 , 2 , 2 , 3 , 3 , 4 , 4 , 5 , 5} , k , m ;
    
25.         m = removeDuplicates(b , 12)                                      ;
    
26.         for(k = 0 ; k < m ; k ++) printf("%d\n" , b[k])                   ;
    
27. }
    

复制代码

风扫地

jackz007 发表于 2019-5-8 03:20
楼主看看这个代码如何

161 / 161 个通过测试用例
状态：通过
执行用时：376 ms


执行用时 : 376 ms, 在Remove Duplicates from Sorted Array的C提交中击败了13.23% 的用户
内存消耗 : 9.6 MB, 在Remove Duplicates from Sorted Array的C提交中击败了74.98% 的用户

赛高，效率比我的提高了接近了一倍~

风扫地

受楼上启发：

1. 
   
2. int removeDuplicates(int* nums, int numsSize)
   
3. {
   
4.     int  len            = 0;
   
5.     int  inner_count    = 0;
   
6.     int  i              = 0;
   
7.     do{
   
8.         /* 输入参数检查,能直接处理的直接处理*/
   
9.         if(  (nums == NULL)
   
10.         ||(numsSize <= 0)
    
11.         )
    
12.         {
    
13.             len = 0;
    
14.             break;
    
15.         }
    
16.         if(numsSize==1)
    
17.         {
    
18.             len = 1;
    
19.             break;
    
20.         }
    
21. 
    
22.         len           = 1;  /* */
    
23.         inner_count   = 1;
    
24.         while(1)
    
25.         {            
    
26.             if(nums[inner_count] != nums[len-1])
    
27.             {
    
28.                 nums[len] = nums[inner_count];
    
29.                 len++;
    
30.             }
    
31.            
    
32.             inner_count++;  /* */
    
33.             if(inner_count > numsSize - 1)
    
34.             {
    
35.                 break;
    
36.             }
    
37.         };
    
38.         
    
39.         break;
    
40.     }while(0);
    
41.     return len;
    
42. 
    
43. }
    

复制代码

执行用时 : 32 ms, 在Remove Duplicates from Sorted Array的C提交中击败了73.08% 的用户
内存消耗 : 9.7 MB, 在Remove Duplicates from Sorted Array的C提交中击败了74.91% 的用户