arrays - 为什么我计算从二维数组中删除一些随机元素的最小步骤数的方法是错误的？

Question

我有一个二维数组，其中在随机位置放置了一些相同的元素，比如 Xs。鉴于我可以通过在一个步骤中删除整行或整列来删除所有此类 X，我必须计算删除所有此类 X 所需的最小步骤数。例如，对于 2x2 数组 [1 表示 (0,0)、(0,1) 和1 代表 (1,0)]

我自己想出了一种方法——我将 x 和 y 坐标存储在两个单独的数组中，然后计算两者中不同的坐标。比较它们，具有最少不同元素的那个就是答案，即，它是所需的最少步骤数。

我已经检查了许多不同的输入，我的答案似乎每次都是正确的。但是，我的老师说这个答案是错误的，尽管他没有解释原因。他只是说它对于特定的测试用例失败了，但他不会提及。

因此，我正在寻求帮助。如果您能找到这种方法的失败之处，请告诉我，我将不胜感激。谢谢。

score 2 · Accepted Answer

假设我理解你的

我将 x 和 y 坐标存储在两个单独的数组中，然后计算两者中的不同坐标。比较它们，具有最少不同元素的那个就是答案，即，它是所需的最少步骤数。

算法正确，那么一个简单的反例是：

  [[1, 1, 1],
   [1, 0, 0],
   [1, 0, 0]]

您将在 a 所在的位置拥有三个不同的 x 坐标和三个不同的 y 坐标1，但显然它只需要两次删除操作。

1 回答 1