c++ - 检查每行/列中的值在 vector 中是否唯一

Question

我想弄清楚如何检查每一行和每一列，看看每列/每行是否有任何重复的数字。

例如，假设一个 3x3 网格得到以下内容:

网格:

{9, 7, 9}

{9, 6, 8}

{5, 1, 4}

第一行有重复的 9，第一列也有重复的 9。

我该如何解决这些问题？

Answer 1

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

你需要有 n unordered_set数据结构。所以最好有一个vector将包含 unordered_set .

定义一个 vector 包含n unordered_set :

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

现在我假设您使用值 0 来阻止特定值, 但是这个假设只有在 0 时才成立。 最初不会出现在您的网格中。

所以基本上我们有一个 unordered_set对于每一列，在位置 (i,j) 处插入元素之前在第 j 个 unordered_set , 我们检查第 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 的解决方案对于列和 n unordered_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;
}