检查每个行/列中的值是否在向量中是唯一的

Question

我想知道如何检查每行&列以查看每列/行是否有任何重复的数字。

举例来说，假设一个3x3栅格得到如下：

网格：

{9, 7, 9} 

{9, 6, 8} 

{5, 1, 4} 

第一行具有9的重复和第一列也具有9.

重复

我该如何解决这些问题？

Answer 1

您可以使用unordered_set数据结构来解决检查重复项的问题。它基于hashtable data structure。关于它的好处是我们可以在恒定时间O（1）中搜索特定元素。阅读更多内容here。

您需要有nunordered_set数据结构。所以最好有一个vector，其中将包含unordered_set。

定义矢量包含nunordered_set：

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

现在我假设您阻止使用值0一个特定的值，但是这种假设是唯一真正的，如果0原本不出现在您的网格 。

所以基本上我们对每列的unordered_set和第j个unordered_set在(i,j)位置插入一个元素之前，我们检查，如果第j个unordered_set含有与否，如果它和它的不为0，那么我们的电网还没有达到解决方案。对于行，我们只保留一个unordered_set,mySet，它在遍历每一行后被清除。

现在你可以实现你的checkSolution()方法是这样的：

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; 
} 

您也可以实现，你必须只有我一个列unordered_set和nunordered_set每个行的解决方案，但你必须遍历网格列主要顺序。

下面是一个示例程序：

#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; 
}