c++ - 有效组合算法过时限

Question

我正在做一个编程练习题，但在这个问题上无法通过时间限制。是否有另一种有效的算法可以通过时间限制？

我已经对数组进行了排序，但我认为这仍然没有多大帮助。

这是我的伪代码:

sort boxA
sort boxB
for i in boxA:
      for j in boxB:
          if i+j < value:
              break
          else if i+j > value:
              count+=1
print the count
set count = 0

题目要求输出有多少个boxA + boxB的组合大于或等于该值。

输入:

5 3 1200                #number of boxA | number of boxB | value
100 110 160 750 1030    #number of boxA
400 500 500             #number of boxB

输出:

5

解释: 有五种方式组合 boxA 和 boxB 使得 value >= value

1. 750 + 500
2. 750 + 500
3. 1030 + 400
4. 1030 + 500
5. 1030 + 500

BoxA 和 boxB 的列表中可以有 500000 个项目。我认为这种测试用例对我的算法造成了时间限制。

你能展示另一种有效的算法来通过这个问题的时间限制吗？谢谢。

Answer 1

对于A中每个有a项的盒子，B中有项目数加上a，大于或等于某个值d的盒子的个数为等于元素数量大于 (d - a) 的箱子数量。

因此，首先，对数组 B 进行排序，然后对于 A 中每个值为 x 的框，使用二分查找从 B 中的索引开始查找，盒子大于或等于 d - x。添加最终结果(n - 索引)，其中 n 是 B 中的项目数。

时间复杂度为O(m log n)

例子:

我们有两个数组 A 是 {1,5,9,2,4,5} 和 B 是 {1,3,3,4,5,6,7,8};

例如，我们想要找到总和大于 7 的两个框。

因此，对于 A 中的每个元素

1 -> 我们使用二进制搜索来查找 B 中大于或等于 (7 - 1) 的最小元素的索引，现在索引为 5，因此我们将结果添加到 (8 - 5)(使用8是B中的元素个数)。

5 -> 我们需要在 B 中找到 (7 - 5) -> 搜索后我们有索引 1 -> 将 (8 - 2) 添加到结果中。

...