0

我正在寻找一种简单的实现算法，该算法可以找到在某一列上具有最大值的表行。然后，它应该在该特定列上找到值接近最大值的所有行（这两个步骤可以组合吗？）。然后，在选定的行中，我需要找到在另一列上具有最小值的行。

奖励：如果有多个这样的条目，我需要在另一列上找到具有最小值的行。

是的，我知道使用 SQL(ite) 很容易做到这一点，但我不想浪费时间将文本文件中的数据解析到数据库表中......

我对如何做到这一点的简单想法感兴趣（伪代码很好），现在，我只能想到一些相当复杂的事情：

  • 遍历所有行并找到最大值
  • 遍历所有行并在列表中插入“接近”最大值的行
  • 在新的行列表中找到最小值
4

2 回答 2

1

其实你在做正确的事。除非您的行值已经排序，否则您无法避免在第 1 步中遍历所有值，因此您最终会花O(R)时间在那里，R行数在哪里。

对于第二步，它的成本也O(R)不会降低算法的复杂性。

如果我们认为“接近最大值”的值的数量是O(1)关于 的R，那么第三步是O(C)其中C的列数。如果您的值未排序，则无法做得比这更好，因为您需要测试所有值才能找到最小值。

您的算法具有您将获得的最佳复杂性。

于 2012-11-01T18:44:09.723 回答
0

我对此的看法：

  • 按行对第一列的表格进行排序
  • 最大值是此排序列中的第一个或最后一个值
  • 所有接近的值都尽可能接近排序列中的最大值
  • 提取那些行
  • 在第二列再次排序
  • 像上面一样找到最小值......
  • 如果有多个这样的条目，请使用第三列再次排序...

其速度由使用的排序算法定义。

于 2012-11-01T18:49:22.847 回答