Skip to content

Latest commit

 

History

History
 
 

079. Remove Duplicates from Sorted Array II

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

这道题是[24. Remove Duplicates from Sorted Array](../24. Remove Duplicates from Sorted Array)的升级版。

我也是根据上一道题的解法,稍作调整。

如,上一道题,如果 n<2, 就没啥可做的,直接返回,到这道题,就变成了 n<3 返回了。因为如果有 0,1 两个位置的元素, 无论它俩是否想等,都应该保留。所以我们的解决方案面对的场景,至少也是 n==3。画个图吧:

1 1 1
  ^ ^
  s i

这算是一种极端情况,s 代表 size,即去重后的数组长度,i 就是迭代下标。由于上面分析了 n==2 无关紧要这个结论, 那么 s 完全可以从 A[1] 开始,而迭代过程,很自然就从 A[2] 开始了。但我们的目标是,上图情况下,s 应该不动,i 继续前行。 故有:

if (A[i] == A[size] && A[i] == A[size-1])
    // size 不动

而继续延展画图:

1 1 1 2 2 3
  ^   ^
 size i

此刻需要 size 前进一位,且赋值为 2 了。故有:

if (A[i] != A[size])
    A[++size] = A[i];

再继续:

1 1 2 2 2 3
    ^   ^
   size i

注意此刻,A[i] == A[size],但 size 显然需要前进一位,因为 2 至少可以出现两次。故有:

if (A[i] != A[size-1])
    A[++size] = A[i];

我们在验证一步:

1 1 2 2 2 3
      ^   ^
    size  i

此刻又符合了之前的情况,能够说明其规律性了。结合三种条件,我们可以发现非常简单:

if (A[i] != A[size] || A[i] != A[size-1])
    A[++size] = A[i];

最后,一定要注意,由于这次用的是前置自加,所以size并不代表真正的长度,而代表着最后一位的位置。所以返回时再自加一次。

OK。