c++ - 大小为 k 的数组(大小为 n)的子集数，最大和最小元素之差最多为 x

Question

我在一次测试中遇到了这个问题。给定一个大小为 n 的数组，找到大小为 k 的子集的数量，其中最大元素和最小元素之差最多为 x。

Constraints 1<=a[i],n,k,x<=10^6
Example:n=5 k=3 x=5 a={1,2,3,4,5}
output: 10

我目前的方法:我首先对数组进行排序并考虑最大的元素。现在使用线性搜索，我找到了最小的元素，其差异小于或等于 x。

现在，如果我选择最大的元素并选择它们之间的任何 k-1 个元素。选择过程是(最大的索引 - 最小的索引)C(k-1)，我总结了这些。

复杂度接近 O(nnk)。我没有被卡住，但我的解决方案无法通过测试用例。

Answer 1

我认为您走在正确的轨道上。据我了解，这是您目前所拥有的:

• 对数组进行排序。
  • 你没有说你是怎么做到的，但是你可以使用基数排序在 O(n) 时间内完成，所以我假设 O(n) 时间。
• 对于每个元素:
  • 计算 E − x 和 E 之间有多少其他元素(其中 E 是这个元素)。调用结果m。
    • 您使用线性搜索在最坏情况下执行此操作的时间为 O(n)。
  • 计算 _mC_k−1。
    • 你没有说你是怎么做到的，但你可以在 O(n) 时间内为所有可能的 m 预先计算它，然后只使用一个常量-time lookup，所以我假设这就是你正在做的。

这种方法给出了正确的结果，并且在最坏情况下需要 O(n²) 时间。 (你提到你得到了 O(n²k) 时间；但我看不出有任何理由。)

您似乎缺少的主要优化是，您可以从前一个元素的线性搜索停止的地方恢复线性搜索，而不是重新开始对每个元素的线性搜索。这样，您所有的线性搜索放在一起 将加起来为线性时间，因为它们相当于只遍历数组一次。 (换句话说，您的线性搜索将有 摊销常数时间。)

这给了我们一个 O(n) 时间的算法:

sort a
precompute nCr(m, k - 1) for all m in (0 .. n-1)
set total_num_subsets := 0
set min_element_index := 0
for max_element_index in 0 .. n-1 do:
    while a[min_element_index] + x < a[max_element_index] do:
        set min_element_index := min_element_index + 1
    set num_eligible_elements := max_element_index - min_element_index
    set num_subsets := nCr(num_eligible_elements, k - 1)
    set total_num_subsets := total_num_subsets + num_subsets

(我们可以做一些额外的小优化——例如，我们可以在 k 而不是 0 开始 max_element_index 迭代，我们可以使用内存而不是预计算来避免计算 _mC_k−1 对于比我们实际最终需要的更大的 m 值——但它们不会改变算法的复杂性。)