计算满足min（子集）max（子集）

Question

在一次采访中被问及这个问题，没有比生成所有可能的子集更好的答案了。例子：

a = [4,2,5,7] k = 8

output = 4

[2],[4,2],[2,5],[4,2,5]

采访者试图暗示对数组进行排序应该会有所帮助，但我仍然无法找到比暴力更好的解决方案。非常感谢您的意见。

Answer 1

1. 对数组进行排序
2. 对于indexl处的元素x，对数组进行二进制搜索以获取数组中最大整数的索引，即

这应该适用于复杂度为0（N*log（N））的情况，足以回答面试问题。

对于给定的示例，排序数组=[2,4,5,7]。

1. 对于元素2，l=0和r=2。Count=2^(2-0) = 4（涵盖[2]，[4,2]，[2,5]，[4,2,5]
2. 对于元素4，l=1和r=0。Count=0，我们打破了迭代。

Answer 2

采访者暗示，对数组进行排序会有帮助，而且确实有帮助。我会尽力解释的。

获取您声明的数组和k值：

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]

将a_排序[ii jj]添加到子集

3.1. Ifa_排序[ii]a_排序[ii jj]

3.1.1. 子集[a_sort[ii]、a_sort[ii jj]持有条件，是解的一部分，以及由任何额外数量的元素组成的任何子集，其中a_sort[kk]

3.1.2。设置jj=1并返回步骤3。

3.2. 否则，设置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\u sort[ii]]，它不包含2*a\u sort[ii]

如果您只是想得到可能的子集，这比生成子集本身更容易。

假设对于ii

看看上面的例子：

• [2]增加1个计数
• [2,4]添加1个计数（1=0 1）
• [2,5]添加2个计数（2=0 2--

总数为4