快捷導(dǎo)航

C語(yǔ)言?詳解如何刪除有序數(shù)組中的重復(fù)項(xiàng)

更新時(shí)間：2022年03月29日 14:57:29 作者：許同學(xué)。。

數(shù)組不擅長(zhǎng)插入（添加）和刪除元素。數(shù)組的優(yōu)點(diǎn)在于它是連續(xù)的，所以查找數(shù)據(jù)速度很快。但這也是它的一個(gè)缺點(diǎn)。正因?yàn)樗沁B續(xù)的，所以當(dāng)插入一個(gè)元素時(shí)，插入點(diǎn)后所有的元素全部都要向后移；而刪除一個(gè)元素時(shí)，刪除點(diǎn)后所有的元素全部都要向前移

刪除有序數(shù)組中的重復(fù)項(xiàng)Ⅰ

a.思路

?定義變量 int dest=0,cur=1，nums[cur]與nums[dest]逐一比較。

?nums[cur]!=nums[dest]，將nums[cur]放入dest下一個(gè)位置，更新dest。

?nums[cur]!=nums[dest]，cur移動(dòng)。

?cur==numsSize，結(jié)束。返回dest+1。

b.圖解

c.代碼

int removeDuplicates(int* nums, int numsSize)
{
    if(numsSize==0)
    {
        return 0;
    }
    int dest=0;
    int cur=1;
    nums[dest]=nums[0];
    //從cur==1  cur<numsSize
    while(cur<numsSize)
    {
        if(nums[cur]!=nums[dest])
        {
            nums[++dest]=nums[cur++];
        }
        else
        {
            cur++;
        }
    }
    return dest+1;    
}

d.思考

?如果給你一個(gè)無(wú)序的數(shù)組，去除重復(fù)的元素，該如何設(shè)計(jì)程序？

刪除有序數(shù)組中的重復(fù)項(xiàng)Ⅱ

a.思路

?定義變量 int dest=0,cur=1,flag=1(表示0到dest,nums[dest]只出現(xiàn)過(guò)一次）。

?比較nums[cur]與nums[dest]。

?nums[cur]!=nums[dest]，將nums[cur]放入dest下一個(gè)位置，++dest，更新flag(flag=1)。

?nums[cur]==nums[dest]，如果dest所對(duì)應(yīng)的flag為1,可將nums[cur]放入dest下一個(gè)位置，++dest， ++flag。如果dest所對(duì)應(yīng)的flag為2，只移動(dòng)cur.。

b.圖解

c.代碼

int removeDuplicates(int* nums, int numsSize)
{
    int dest=0;
    int cur=1;
    int flag=1;
    nums[dest]=nums[0];
    //從cur==1到cur<numsSize
    while(cur<numsSize)
    {
        if(nums[cur]!=nums[dest])
        {
            nums[++dest]=nums[cur++];
            flag=1;
        }
        else
        {
            if(flag==1)
            {
                nums[++dest]=nums[cur++];
                ++flag;
            }
            else
            {
                cur++;
            }
        }
    }
    return dest+1;
}