在采访中被问到这个问题,没有比生成所有可能的子集更好的答案了。 示例:
a = [4,2,5,7] k = 8
output = 4
[2],[4,2],[2,5],[4,2,5]
面试官试图暗示对数组进行排序应该会有帮助,但我仍然想不出比蛮力更好的解决方案。将感谢您的意见。
最佳答案
面试官暗示对数组进行排序会有所帮助,而且确实有帮助。我会尽力解释。
获取数组和k
您陈述的值(value)观:
a = [4,2,5,7]
k = 8
对数组进行排序将产生:
a_sort = [2,4,5,7]
现在我们可以考虑以下过程:
设置 ii = 0, jj = 1
选择
a_sort[ii]
作为你子集的一部分2.1。如果
2 * a_sort[ii] >= k
,你完成了。否则,子集[a_sort[ii]]
满足条件并且是解决方案的一部分。添加
a_sort[ii+jj]
到你的子集3.1。如果
a_sort[ii] + a_sort[ii+jj] < k
,3.1.1。子集
[a_sort[ii], a_sort[ii+jj]]
满足条件并且是解决方案的一部分,以及由任何额外数量的元素组成的任何子集a_sort[kk]
其中ii< kk < ii+jj
3.1.2。设置
jj += 1
并返回第 3 步。3.2。否则,
set ii += 1
,jj = ii + 1
, 回到第2步
根据您的输入,此过程应返回:
[[2], [2,4],[2,5],[2,4,5]]
# [2,7] results in 9 > 8 and therefore you move to [4]
# Note that for [4] subset you get 8 = 8 which is not smaller than 8, we are done
解释
- 如果你有一个 [a_sort[ii]] 的子集不满足
2 * a_sort[ii] < k
, 向子集添加额外的数字只会产生min(subset)+max(subset) > 2 * a_sort[ii] > k and therefore there will not be any additional subsets which hold the wanted condition. Moreover, by setting a subset of [a_sort[ii+1]] will results in
2 * a_sort[ii+1] >= 2 * a_sort[ii] > k` 因为 a_sort 已排序。因此,您不会找到任何其他子集。 - 对于 jj > ii,如果
a_sort[ii] + a_sort[ii+jj] < k
如果来自a_sort
的成员,您可以推送任何号码进入子集,只要索引kk
将大于ii
低于ii+jj
自a_sort
已排序,将这些成员加入子集不会改变min(subset)+max(subset)
的值这将保留a_sort[ii] + a_sort[ii+jj]
我们已经知道这个值更小谢谢k
获取计数
如果您只是想要可能的子集,这比自己生成子集更容易。
假设 ii > jj
条件成立,即 a_sort[ii] + a_sort[ii+jj] < k
.如果jj = ii + 1
增加了 1 个可能的子集。如果jj > ii + 1
有jj - ii - 1
在不改变值 a_sort[ii] + a_sort[ii+jj]
的情况下可以存在的附加元素.因此共有 2**(jj-ii-1)
可用于添加到解决方案组的其他子集(jj-ii-1
元素,每个元素是否独立存在)。这也适用于 jj = ii + 1
因为在这种情况下 2**(jj-ii-1) = 2**0 = 1
看上面的例子:
- [2] 加 1 个计数
- [2,4] 添加 1 个计数 (
1 = 0 + 1
) - [2,5] 添加 2 个计数 (
2 = 0 + 2
-->2 **(2 - 0 - 1) = 2**1 = 2
)
总计 4
关于algorithm - 计算符合 min(subset)+max(subset) < k 的数组子集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/71546296/