檢測二維數組中列的重複

Question

我想要一個算法，通過二維數組，並保證每列都有不同的數字。如果在數組中找到了一個重複的數字，它應該用一個隨機數字替換。隨機數還必須保持唯一性。

如果我們放一個隨機數，整列應該是唯一的。

是否有可能獲得O（N）解決方案？

Answer 1

我能想到的最好方法是爲每列創建一個unordered_map<int,bool>，迭代遍歷列，並且如果您第一次看到一個數字，則將該映射設置爲true，如果該值已爲true，則它是一個僞造替換它帶有一個隨機數。然後檢查地圖中的隨機數，並做同樣的事情，如果這也是一個愚蠢的事情，你將不得不用一個隨機數再次替換它。這個算法會喜歡在線性時間運行，但是由於隨機數的可能性，它可以無限運行。

僞代碼

2d_array // assume M rows by N cols 
array_of_hashtables // N length 
for each col 
    for each row 
     if array_of_hashtables[2d_array[row][col]] == false 
      set it to true 
     else 
      do 
       set 2d_array[row][col] to random 
      while array_of_hashtables[2d_array[row][col]] == true 
    end 
end 

不寫僞代碼的一個巨大的風扇，但是這是對的

Answer 2

做一個std::set並插入一步每一列的一步元素，同時檢查的大小組。如果大小更改，插入的值不是重複的，如果它只是隨機化一個值並將其重新添加到集合中。如果大小改變，你可以繼續。

Answer 3

只爲它赫克，這裏是Alexandru Barbarosie的解決方案的實現：

#include <iostream> 
#include <set> 
#include <cstdlib> 
#include <ctime> 

using namespace std; 

int main() 
{ 
    int L = 3; 
    int W = 3; 
    int R = 3;  
    int a[L][W];  
    srand(time(NULL));  
    for (int i = 0; i < L; i++) 
    { 
     for (int j = 0; j < W; j++) 
     { 
      a[i][j] = rand() % R + 1; 
      cout << a[i][j] << " "; 
     } 
     cout << endl; 
    }  
    cout << endl; 

    set<int> s;  
    int n = 0;  
    for (int j = 0; j < W; j++) 
    { 
     for (int i = 0; i < L; i++) 
     { 
      s.insert(a[i][j]); 
      if (s.size() != n) 
       n = s.size(); 
      else 
       a[i--][j] = rand() % R + 1; 
     } 
     s.clear(); 
     n = 0; 
    } 

    for (int i = 0; i < L; i++) 
    { 
     for (int j = 0; j < W; j++) 
      cout << a[i][j] << " "; 
     cout << endl; 
    } 
}