时间戳

首页 > 解决方案 > 如何在 Multiset-sum 中找到第 K 个最小元素？

algorithm - 如何在 Multiset-sum 中找到第 K 个最小元素？

问题描述

需要一些帮助来设计一个算法来解决这个问题。

令a和b为 a ≤ b 的整数，令 [a,b] 表示集合 {a, a + 1, a + 2, ..., b}。假设我们有n 个这样的集合，[a 1 ,b 1 ],...[a n ,b n ]，它们的多集和是

S = {a 1 , a 1 + 1,..., b 1 , a 2 ,a 2 + 1,...,b 2 ,...,a n ,a n + 1, ..., b } _

例如，[5,25]、[3,10] 和 [8,12] 的多集和是

{3,4,5,5,6,6,7,7,8,8,8,9,9,9,10,10,10,...,25}

给定集合[a 1 , b 1 ],...,[a n , b n ] 使得 0 ≤ a i , b i ≤ N 且整数 k > 0，设计一个输出 k 最小元素的有效算法在 S 中，集合的多重集合和。根据 n 和 N 确定算法的运行时间。

我已经设计了两个辅助算法，称为 FindElementsBefore(x, [a 1 ,b 1 ]...[a n ,b n ]) 和 FindElementsAfter(x, [a 1 ,b 1 ]...[a n , b n ]）。它们都接受一个元素 x 和每个集合，并分别返回 S 中小于 x 和大于 x 的元素数。

我的教授告诉我，使用这两种辅助方法，我应该能够解决上述问题，但我完全被难住了。我该如何解决这个问题？

标签： algorithmbig-oanalysis

解决方案

使用二进制搜索。

您已经知道 multiset-sum 中的最大值和最小值。因此，您有第 k 个最小元素的上限和下限。现在您可以简单地递归上限和下限，具体取决于FindElementsBefore(mid, ...) <= k.

推荐阅读