java - 在某些条件下在矩阵中查找相同的数字

Question

我有编程竞赛的问题。这个问题在某些时候很容易。我写了一个解决方案，效果不是很好。我想听听您对这个问题的看法，您将如何设法在更“好的”编程中解决此类问题。

问题:

Write a program that will have as an input an N*N array. This array contains integer numbers. You should find how many different numbers are there with the following condition: Different number is also:

A) Numbers that are the same but is next each of other. e.g 1 1 can be thought as one number because are the same numbers and next to each other.

B) The (A) to be true, the if you have for example Number 1, then any SAME numbers at left, right, top and down are also the same.

例如

1 1 2 3

1 2 3 4

2 2 1 3

所以对于上面，有 8 个不同的数字。这是因为，在数组 [0,0] 中，[0, 1] 和 [1,0] 可以被认为是一个数字而不是 3 个不同的数字。 [1,1],[2,1] 因此 [2,0] 也是相同的数字。因此，正如您在最后一个数字中看到的那样，[1,1]、[2,1] 确实暗示了条件，然后 [2,0]、[2,1] 也暗示了条件，但是因为 [2,1 ] 也暗示条件 [1,1] 因此所有 [1,1]、[2,1] 和 [2,0] 都是一个数字。

我的代码:

public class matrix
{
   public static void main(String[] args)
   {
      int[][] arr = 
      { 
          {1, 2, 3, 4}, 
          {1, 1, 2, 4},
          {5, 6, 2, 2},
      };

      for(int row = 0; row < arr.length; ++row)
      {
         for(int col = 0; col < arr[row].length; ++col)
         {
            //top
            if(row!=0)
            {
               if((arr[row][col] == arr[row-1][col]) || (Math.abs(arr[row][col]) == arr[row-1][col]) || (arr[row][col] == Math.abs(arr[row-1][col])))
               {
                  arr[row-1][col] = -arr[row-1][col];
               }
            }

            //botom
            if(row!=arr.length-1)
            {
               if(arr[row][col] == arr[row+1][col] || Math.abs(arr[row][col]) == arr[row+1][col] || arr[row][col] == Math.abs(arr[row+1][col]))
               {
                  arr[row+1][col] = -arr[row+1][col];
               }
            }

            //left
            if(col!=0)
            {
               if(arr[row][col] == arr[row][col-1] || Math.abs(arr[row][col]) == arr[row][col-1] || arr[row][col] == Math.abs(arr[row][col-1]))
               {
                  arr[row][col-1] = -arr[row][col-1];
               }
            }

            //right
            if(col!=arr[0].length-1)
            {
               if(arr[row][col] == arr[row][col+1] || Math.abs(arr[row][col]) == arr[row][col+1] || arr[row][col] == Math.abs(arr[row][col+1]))
               {
                  arr[row][col+1] = -arr[row][col+1];
               }
            }
         }
      }


      for(int row = 0; row < arr.length; ++row)
      {
         for(int col = 0; col < arr[row].length; ++col)
         {
            System.out.print(arr[row][col] + " ");
         }

         System.out.println();
      }
   }
}

我的逻辑是将相同的数字设置为负数，然后只计算正数以找到不同的数字。
我想要一种不同的算法来产生更小的 Big-O 复杂度。

谢谢。

Answer 1

如果我对你的问题理解正确的话，你可以把它看成一个图形问题，计算连通分量的数量。

例如，让矩阵中的每一项成为一个顶点(用行-列标记)，所以 (0,0) 是一个顶点(值为 1)。那么，如果两个顶点直接在彼此的上方、下方、右侧或左侧并且具有相同的值，则这两个顶点是相邻的。例如 (0,0) 与 (0,1) 相邻，因为两者的值为 1。(0,1) 不与 (0,2) 相邻，因为第一个的值为 1，第二个的值为 2。然后你数图表中连接的组件的数量。每个连接的组件代表一个“不同”的数字。

有很多方法可以快速计算连接组件的数量。例如，从顶点 (0,0) 开始，进行广度优先搜索。您找到的任何顶点都在与 (0,0) 相同的组件中。然后从任何尚未找到的顶点开始重复。广度优先搜索是线性时间，但你必须运行它几次(假设你运行它的次数越多，每次运行的速度就越快)所以确定确切的渐近运行时间有点复杂。您的输入大小为 n^2(顶点数)。它不会比 n^3 差，并且可能更接近 n^2(请记住 n^2 表示“输入大小的线性”)。