如何避免C數組中的重複元素項？

Question

我要一些邏輯將所述陣列中插入數字，並在同一時間它會檢查當前的號碼已不存在在數組中。請幫助我的邏輯。

Answer 1

代碼以在數組中刪除重複的元素

#include<stdio.h> 
    #include<conio.h> 
    void main() 
    { 
     int a[20], i, j, k, n; 
     clrscr(); 

     printf("\nEnter array size : "); 
     scanf("%d",&n); 

     printf("\nEnter %d array element : ", n); 
     for(i = 0; i < n; i++) 
     { 
      scanf("%d",&a[i]); 
     } 

     printf("\nOriginal array is : "); 
     for(i=0;i< n;i++) 
     { 
      printf(" %d",a[i]); 
     } 

     printf("\nNew array is : "); 
     for(i=0; i < n; i++) 
     { 
      for(j=i+1; j < n;) 
      { 
      if(a[j] == a[i]) 
      { 
       for(k=j; k < n;k++) 
       { 
        a[k] = a[k+1]; 
       } 
       n--; 
      } 
      else { 
       j++; 
      } 
      } 
     } 

     for(i=0; i < n; i++) 
     { 
      printf("%d ", a[i]); 
     } 
    getch(); 
    } 

輸出

輸入數組大小：5

輸入5的數組元素：11 13 11 12 13

原始陣列是：11 13 11 12 13

新陣列是：11 13 12

Answer 2

可能的解決方案：

1. O(n^2)算法，在這裏做線性搜索O(n)檢查該號碼是否存在於陣列中或不是所有的n元素。

對於每個元素（n個元素）：

O(n)：搜索

O(1)：插入

O(n^2)算法，當你在排序後的數組插入。

對於每個元素（n個元素）：

O(log n)：二進制搜索

O(n)：移動和插入

雖然有先進的數據結構（更多在C++ STL），但你將需要的不僅僅是一個數組。因爲在數組中插入代價很大（在特定位置插入）。

其他數據結構這可能幫助：BST（AVL-BST，伸展樹......等平衡樹結構）。

在C++：套正是你想要的。集合在STL中作爲樹實現。