如何找到二维数组所有列的最佳匹配？

Question

假设我有一个如下所示的二维数组：

________________
|10|15|14|20|30|
|14|10|73|71|55|
|73|30|42|84|74|
|14|74|XX|15|10|
----------------

正如我所示，列的大小不需要相同。

现在我需要找到每一列的最佳匹配（具有最完全相同的项目和最低的差异的那一列）。当然，我可以在 n^2 中做到这一点，但这对我来说太慢了。我该怎么做呢？

我考虑过一棵 k 维树并为每个树找到最近的邻居，但我不知道它是否好并且它会按我想要的方式工作（可能不会）。

结果例如：

• 第​​一列很可能是第三列（只有三个不同 - 10、14、42）
• 第二列 ->第五个（只有两个不同 - 15 和 55）

等等等等...:)

Answer 1

如果您知道表中的所有数字都是 2 位数字（即 10 =< x <100），则为每一列创建一个布尔数组，您将在其中标记现有数字：

bool array[5][100];
std::fill( &array[0][0], &array[0][0] + sizeof(array) , false ); // init to false
for (int i = 0; i < 5; i++)
{
  for (int j = 0; j <5; j++)
  {
     array[i][table[i][j]] = true;
  }
}

从那里应该很容易。