避免二維數組中的重複？

我正在做一個C程序，它需要將一組值（整數）轉換爲二維數組，然後對其執行某些數學運算。我決定在用戶輸入值時，在程序中執行檢查，以避免它們輸入已存在於數組中的值。避免二維數組中的重複？

但我不確定如何去做這個檢查。我發現我可能需要某種遞歸函數來檢查輸入的元素之前的所有元素，但我不知道如何實現它。

請找我的用於說明目的的代碼片段如下：

ROW和COL的值由用戶輸入該陣列的尺寸

for (int i=0; i<row;i++){ 
    for (int j=0; j<col; j++){ 
     scanf("%d", &arr[i][j]); //take in elements 
    } 
} 
for (int i = 0; i < row; i++) 
    { 
     for (int j = 0; i < col; j++) 
     { 
      if (arr[i][j] == arr[i][j-1]){ 
       printf("Duplicate.\n");} 
      else {} 
      } 

    }

我知道這可能是不正確的，但這是我的嘗試。任何幫助將不勝感激。

來源

2017-04-25 Lorenzo Battilocchi

可以對一個或兩個維度中的值進行排序嗎？ – BurnsBA

對於一維數組，我沒有任何問題，但事實上這是一個二維數組，它使我很困惑...... @BurnsBA –

你知道'='不是比較運算符，對嗎？ – user694733

我會建議您存儲您在臨時一維數組中讀取的每個元素。每次掃描一個新元素時，遍歷一維數組檢查值是否存在。雖然這不是最佳的，但每次都會比遍歷2D陣列便宜。

實施例：

int temp[SIZE]; 
int k,elements = 0; 
for (int i = 0; i < row; i++) { 
    for (int j = 0; j < col; j++) { 
     scanf("%d", &arr[i][j]); //take in elements 
     temp[elements] = arr[i][j]; 
     elements++; 
     for (int k = 0; k < elements; k++) { 
      if (temp[k] == arr[i][j]) 
       printf("Duplicate.\n"); //or do whatever you wish 
     } 
    } 
}

來源

2017-04-25 14:05:11

在C中，二維數組的實現與1D相同，所以差異可以忽略不計。 –

@ivan_pozdeev呃，不，它們被實現爲一維數組的一維數組。佈局當然是第二行的元素，緊跟在第一行的元素之後，沒有附加的填充，標準保證了這一點。但是，這不允許將二維數組打到「int *」類型，並將數據作爲一維數組訪問（如for（int i = 0; i cmaster

@cmaster [是嗎？]（http://stackoverflow.com/questions/ 2151084/map-a-2d-array-on-a-1d-array-c/33406032＃33406032） –

甲balanced tree插入和搜索在爲O（log N）時間。

由於算法非常簡單&標準和高德納，there are plenty of implementations out there發表在開創性的著作，包括a clear and concise one at codereview.SE（因而是自動CC-BY-SA 3.0; 做在答題應用修正錯誤）。使用它（以及幾乎任何其他）很簡單：以node* root = NULL;，然後insert和search，最後free_tree開始。

漸近，最好的方法是hash table與O（1）兩個，但是這可能是矯枉過正（的算法更復雜和內存佔用較大），除非你有很多數字爲。對於C++，有一個標準實現，但there are plenty 3rd-party ones for C也是。

如果你的輸入值的數量少，連樹可能是矯枉過正，並簡單地翻翻以前的值就足夠快。 If your 2D array is contiguous in memory, you can access it as 1D with int* arr1d = (int*)&arr2d。

來源

2017-04-25 14:43:13

沒有。漸近地說，最好的算法是一個哈希表：它在O（1）時間插入和搜索。 – cmaster

@cmaster哦，sh＃t，我忘記了哈希表！但這絕對是一個矯枉過正的問題。 –

哈希表對此過度殺傷:-) – cmaster

避免二維數組中的重複？

回答

相關問題