python - 如何在指数级大列表中找到第 k 个最大的元素？
问题描述
假设有n组实数：S[1], S[2], ..., S[n]。我们知道关于这些集合的两件事：
每个集合 S[i] 正好有 3 个元素。
每个集合 S[i] 中的所有元素都是 [0, 1] 范围内的实数。（不过，我不知道这个细节是否对解决方案有所帮助）。
让我们考虑一组T可以表示为的所有数字，p[1] * p[2] * p[3] * ... * p[n]其中 p[i] 是 S[i] 的一个元素。T显然，这个 set有 3^n 个元素。
我的问题是，给定集合(1 <= n <= 30) 和一些 1 <= k <= 10 作为输入，我们能比 O(3^n) 更快地S[1], S[2], ..., S[n]找到第 k 个最大数吗？T重要的是，我不仅需要第 k 个最大的数字，还p[1], p[2], p[3], ... , p[n]需要产生它的相应数字 ( )。
即使答案是否定的，我也会很感激有关您如何通过使用一些启发式方法来近似解决这个问题的任何提示？我知道光束搜索，但也许你可以提出其他建议？即使对于波束搜索，也不清楚如何在这里以最佳方式实现它。
如果可以在少于 O(3^n) 的时间内通过算法获得确切的答案，如果您能指出解决方案，我将不胜感激。
解决方案
好吧，您知道最大的产品是使用每组中最大因子的产品。
此外，所有其他产品都可以通过从一个较大的产品开始，然后减少恰好在一组中选择的因子来形成。
这导致一个简单的搜索：
将最大的产品放入最大优先级队列。
重复 k 次：
一个。从优先级队列中移除最大的产品 p
湾。对于每个集合的数字小于 p 中选择的集合，生成通过将该数字减少到该集合中的下一个较小的数字而形成的乘积。如果以前从未见过这种因素选择，则将其添加到优先级队列中。
产品将按降序从队列中删除，因此您取出的第 k 个是第 k 个最大的。
复杂度约为 N*(k log kN)，具体取决于您实现事物的方式。
请注意，可能有多种方法可以选择产生相同产品的因素。该解决方案将这些方式视为不同的产品，即，在找到第 k 个最大的时计算每种方式。这可能是也可能不是你想要的。