各行/列の値がベクトル内で一意であるかどうかを調べる

Question

各行/行ごとに数値が重複していないか確認するために、各行のチェック方法を調べようとしています。例えば

、3×3のグリッドは、以下を取得言う：

グリッド：

{9, 7, 9} 

{9, 6, 8} 

{5, 1, 4} 

最初の行9の重複を有し、第1の列も9

の重複を有します

どうすればこれらの問題を解決できますか？

Answer 1

unordered_setデータ構造を使用すると、重複をチェックする際の問題を解決できます。それはhashtable data structureに基づいています。良いことは、一定時間O（1）で特定の要素を検索できることです。詳しくはhereをご覧ください。

nunordered_setのデータ構造が必要です。だからunordered_setを含むvectorを持つ方が良いです。

がnunordered_setを格納するためのベクトルを定義します。

vector<unordered_set<int>> mySets(n); 

を今、私はあなたが値0を使用して特定の値をブロックすることを想定しています、しかし、0はもともとあなたのグリッドに表示されない場合には、この仮定は唯一の真実であります。

だから、基本的に、我々は各列のunordered_setを持っており、それがないとそのない0場合はj番目unordered_setは、それが含まれているかどうj番目unordered_setに位置(i,j)に要素を挿入する前に、私たちは、その後、確認してくださいグリッドは解決策に達していません。そして、行のために我々はただ一つのunordered_set、mySetを保持し、各行を横断した後にクリアされます。

bool checkSolution() 
{ 
    unordered_set<int> mySet;//for each row 
    for (size_t i=0;i<myGrid.size();i++) 
    { 

     for (size_t j=0;j<myGrid[i].size();j++) 
     { 
      if(mySets[j].find(myGrid[i][j]) != mySets[j].end() && myGrid[i][j] != 0) 
      return false; 
      else 
      mySets[j].insert(myGrid[i][j]); 
      if(mySet.find(myGrid[i][j]) != mySet.end() && myGrid[i][j] != 0) 
      return false; 
      else 
      mySet.insert(myGrid[i][j]); 
     } 

     mySet.clear(); 
    } 
    return true; 
} 

また、あなたはそれぞれの行のためのちょうど1の列のunordered_setとnunordered_setを持っているソリューションを実装することができますが、その後はトラバースする必要があります。

は今、あなたはこのようなあなたの checkSolution()メソッドを実装することができますグリッドを列の大きな順に並べ替えます。

#include<iostream> 
#include<vector> 
#include<unordered_set> 

using namespace std; 
bool checkSolution(); 
int myGrid[3][3] = {{0,2,3}, 
        {4,5,6}, 
        {0,8,9}};// 0 indicates blocked values 


int main() 
{ 
    if(checkSolution()) 
    cout<<"No duplicates exist"; 
    else cout<<"Duplicates exist"; 

} 
bool checkSolution() 
{ 
    int n = 3; 
    vector<unordered_set<int> > mySets(n); 
    unordered_set<int> mySet; 
    for(int i = 0;i < sizeof(myGrid)/sizeof(myGrid[0]); ++i) 
    { 
     for(int j = 0;j < sizeof(myGrid[i])/sizeof(myGrid[0][0]);++j) 
     { 
      if(mySets[j].find(myGrid[i][j]) != mySets[j].end() && myGrid[i][j] != 0) 
       return false; 
      else mySets[j].insert(myGrid[i][j]); 
      if(mySet.find(myGrid[i][j]) != mySet.end() && myGrid[i][j] != 0) 
       return false; 
      else mySet.insert(myGrid[i][j]); 
     } 
     mySet.clear(); 
    } 
    return true; 
}