这道题是[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。