gpt4 book ai didi

algorithm - 计算符合 min(subset)+max(subset) < k 的数组子集

转载 作者:行者123 更新时间:2023-12-02 15:55:44 27 4
gpt4 key购买 nike

在采访中被问到这个问题,没有比生成所有可能的子集更好的答案了。示例:

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]

现在我们可以考虑以下过程:

  1. 设置 ii = 0, jj = 1

  2. 选择 a_sort[ii]作为你子集的一部分

    2.1。如果2 * a_sort[ii] >= k ,你完成了。否则,子集 [a_sort[ii]]满足条件并且是解决方案的一部分。

  3. 添加 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+jja_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 + 1jj - 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/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com