Remove Duplicates

这是一道简单程设,但是写起来还是不利索,写链表版更麻烦了,本来这种中间插入删除是利于用链表的,但是先试试数组版的,
至少这些都需要,思路比较简单,找count>2 的多出来的区间,删掉就可以了,思考的过程如下:

  1. 找多出2的重复数,while里面有a[i]=a[i+1],一开始写的a[i] a[i-1] 但是后面找多出重复数区间又是a[]i a[i+1],然后意识到
    统一比较好,于是前面也改成a[i] a[i+1]

2.有i+1 i++ 想到越界,前面加上i<=n-1, 后面才想到长度在变,要用length,或者直接n 来变也行

  1. count<2 初始count=1, 一开始以为count=3 可以少一种while exit条件的讨论,后来发现不行

4.while(i<=length-2 && a[i]==a[i+1] && count<2) 退出循环有8中情况,我们来一层层博洋葱,如果越界了,一定是count<="2" 因为如果count前面="2" 就退出循环不会到这一轮了,越界了自然没有a[i+1]="" 也没有a[i]="" a[i+1]关系的概念了。count<="2" 没有删除元素直接返回或者break循环即可,一次剥掉4种情况。="" 后面i<="length-2," a[i]!="a[i+1]" 同上分析必count<="2," 那么没有需要删除的元素,直接continue下一轮while,注意i要后移,同时我submit漏了count="1,因为每一次while开始都必须保证" count清为1,至少重复一次。接下来就是正常的了,count<="2," 且a[i]="=a[i+1]" 说明重复元素="">=3, 然后后面注意控制,一个while找重复区间,注意同样不越界,类似前述分析,然后最后一定记得length或n要减去[start, end] 区间长度,end-start+1, 最后i=start,
表示后移元素的第一个的新的位置

其实这样一个简单的程设里面包含的条件分析也很多的,最开始学的时候,这个肯定会出很多错误,关键是while退出条件的分析,
这就像一套规则要适用所有数据,其实是不简单的。

class Solution {
public:
    int removeDuplicates(int a[], int n) {
        int count=1;
        int i=0,start,end,length=n;
        while(i<length)
        {
            while(i<=length-2 && a[i]==a[i+1] && count<2)
                count++,i++;
            if(i>=length-1)
            {
                break;
            }
            if(a[i]!=a[i+1])
            {
                i++;
                count=1;
                continue;
            }
            i++;
            start=i;
            while(i<=length-2 && a[i]==a[i+1])
                i++;
            end=i;
            //delete(start,end);
            count=1;
            for(int l=start,m=end+1;m<=length-1;l++,m++)
                a[l]=a[m];
            length-=(end-start+1);
            //a[start+1]=a[end+2];
            //...
            //=a[n-1];

            i=start;
        }
        return length;
    }
};

Posted by richard爱闹 - 8月 6 2014
如需转载,请注明: 本文来自 Richard