java—如何在忽略一个特定值的情况下在矩阵/数组中查找重复项?

mwkjh3gx  于 2021-06-27  发布在  Java
关注(0)|答案(1)|浏览(345)

我正在用java编写一个sodoku游戏,其中一条规则是每一行不能多次包含相同的数字(1-9)。数字0表示该框为空。如果发现重复项,我的“checkrow”布尔方法应该返回“false”,如果没有找到重复项,则返回“true”(正确的行)。我知道如何查找重复项,但由于值“0”表示空框,因此允许重复“0”。
我如何做到这一点?
这是我到目前为止想出的代码。它在每个测试用例中都返回“true”(未找到重复项)。

public boolean checkRow(int row){

       for (int k = 0; k < grid.length; k++){
            for (int i = k + 1; i < grid.length; i++){
                if (grid[row][k] == (grid[row][i]) && grid[row][k] != 0) {
                    return false;                       
        }
    }
}
return true;
}

使用加法数组存储找到的值的代码:

public boolean checkRow(int row){

  int[] found = new int[9];
  for (int k = 0; k < grid.length; k++){
      if (grid[row][k] > 0 && grid[row][k] < 10){
          found[grid[row][k]]++;
      }

      if (found[grid[row][k]] > 1){
          return false;
      }

     }
    return true;                
}

这也只返回true。
提前谢谢!

ddarikpa

ddarikpa1#

根据@thomas comment,解决方案可以如下(不使用全局 grid 变量)

public static boolean isRowValid(int[] row) {
    int[] freq = new int[9];

    for (int num : row) {
        if (num > 0 && freq[num - 1]++ > 0) {
            // debugging print
            System.out.printf("Duplicate %d found%n", num);
            return false;
        }
    }
    return true;
}

测试

int[][] grid = {
    {1, 2, 3, 4, 5, 6, 7, 8, 9},
    {0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 1, 0, 0, 2, 0, 0, 8, 0},
    {0, 1, 0, 0, 2, 0, 0, 1, 0},
    {1, 2, 3, 4, 5, 6, 7, 8, 1},
    {1, 2, 3, 4, 1, 6, 7, 8, 9},
    {0, 2, 0, 3, 1, 4, 0, 1, 1},
    {3, 2, 0, 1, 3, 0, 3, 0, 0},
    {7, 2, 0, 1, 3, 0, 3, 0, 7},
};

for (int[] row : grid) {
    System.out.printf("Row %s has no dups? %s%n", Arrays.toString(row), isRowValid(row));
}

输出

Row [1, 2, 3, 4, 5, 6, 7, 8, 9] has no dups? true
Row [0, 0, 0, 0, 0, 0, 0, 0, 0] has no dups? true
Row [0, 1, 0, 0, 2, 0, 0, 8, 0] has no dups? true
Duplicate 1 found
Row [0, 1, 0, 0, 2, 0, 0, 1, 0] has no dups? false
Duplicate 1 found
Row [1, 2, 3, 4, 5, 6, 7, 8, 1] has no dups? false
Duplicate 1 found
Row [1, 2, 3, 4, 1, 6, 7, 8, 9] has no dups? false
Duplicate 1 found
Row [0, 2, 0, 3, 1, 4, 0, 1, 1] has no dups? false
Duplicate 3 found
Row [3, 2, 0, 1, 3, 0, 3, 0, 0] has no dups? false
Duplicate 3 found
Row [7, 2, 0, 1, 3, 0, 3, 0, 7] has no dups? false

使用流api的等效解决方案如下所示:

public static boolean isRowValidStream(int[] row) {
    int[] freq = new int[9];
    return Arrays.stream(row) // getIntStream
                 .filter(x -> x > 0) // filter out all zeroes
                 .map(x -> freq[x - 1]++) // calculate frequency
                 .noneMatch(f -> f > 0); // look for the first frequency value 1 
}

相关问题