删除數組中相同元素(C語言)

删除數組中的相同元素(C語言實作)

1.思路一:周遊數組每一個元素,然後再周遊該元素之後的元素,若沒有相同的,則該元素不被删去,可以将它存在另一數組中(這裡,邏輯上可以将原數組看作兩個數組,一會看代碼)

#include <stdio.h>

int del_same(int date[],int n);

int del_same(int date[],int n)
{
    int i,j,k=0;
    for(i=0;i<n;++i)//i用來周遊數組
    {
        for(j=i+1;j<n && date[i]-date[j];++j);
        if(!(j-n))//沒有重複元素
            date[k++]=date[i];//可将date[]看作兩個數組
    }
    return k;//傳回删除後的有效長度
}

int main(void)
{
    int date[1001],i,j,k,n;
    printf("輸入資料個數:");
    scanf("%d",&n);
    printf("輸入資料:");
    for(i=0;i<n;++i)
        scanf("%d",date+i);

    k=del_same(date,n);
    for(i=0;i<k;++i)
        printf("%-5d",date[i]);

    return 0;
} 
//也可以找相同的,然後讓剩下的前移,可以删實作删除
           

時間複雜度O(N²)

思路2:首先将數組進行排序,這樣相同的元素就會"在一起",然後周遊數組,這樣也可以實作删除相同元素

#include <stdio.h>

void sort(int date[],int n);
int del_same(int date[],int n);
//這是一個簡單的選擇排序
void sort(int date[],int n)
{
    int i,j,k,t;
    for(i=0;i<n-1;++i)
    {
        k=i;
        for(j=i+1;j<n;++j)
        {
            if(date[k]>date[j])
                k=j;
        }
        t=date[k];
        date[k]=date[i];
        date[i]=t;
    }
}
//這裡的傳回值為删除後的有效長度
int del_same(int date[],int n)
{
    int i,j,k;
    k=0;
    for(i=0;i<n;++i)
    {
        if(date[i]-date[i+1])//不一樣就存到該數組(邏輯上可看作另一數組)
            date[k++]=date[i];
    }
    /*特别說明下這裡,下面的語句是為了避免數組最後一個元素與date[n]處的随機值相同,
      若沒有下面的語句,可能會漏掉最後一個元素(機率較低,但可能發生)*/
    date[k++]=date[n-1];
    if(date[k-1]==date[k-2])
        --k;
    return k;
}

int main(void)
{
    int date[1001];
    int n,len;
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%d",date+i);

    sort(date,n);
    len=del_same(date,n);

    for(int i=0;i<len;++i)
        printf("%-5d",date[i]);

    return 0;
}
           

時間複雜度O(N²),時間主要浪費在排序上

方案3:運用類似桶排序的方法,浪費空間來換取時間,這個方案需要直到資料的範圍

#include <stdio.h>

int main(void)
{
    int date[1001],book[1001]={0};//先将數組初始化為零
    int n,i,j,k;
    scanf("%d",&n);
    for(i=0;i<n;++i)
    {
        scanf("%d",&j);
        ++book[j];//将資料所在的單元自增
    }

    k=0;
    for(i=0;i<1001;++i)
    {
        if(book[i])//那些單元裡面值不為0的說明有這個資料
            date[k++]=i;
    }
    for(i=0;i<k;++i)
        printf("%-5d",date[i]);

    return 0;
}
           

時間複雜度O(N)

可以看到,雖然時間複雜度不高,但是對于空間的消耗比較大上述的例子資料的範圍是1~1000,是以該方法要知道資料的範圍才可以保證不出錯

2018/5/28 23:36:24