在一次采訪中被問到這個問題，沒有比生成所有可能的子集更好的答案了。例子：
a = [4,2,5,7] k = 8
output = 4
[2],[4,2],[2,5],[4,2,5]
面試官試圖暗示對陣列進行排序應該會有所幫助，但我仍然想不出一個比蠻力更好的解決方案。將感謝您的意見。
uj5u.com熱心網友回復：
面試官暗示對陣列進行排序會有所幫助，而且確實有幫助。我會盡力解釋。
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] >= 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 jj3.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 in2 * a_sort[ii 1] >= 2 * a_sort[ii] > k` 因為 a_sort 已排序。因此，您不會找到任何其他子集。 - 對于 jj > ii，如果
a_sort[ii] a_sort[ii jj] < k然后您可以將任何數字 if 成員從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
uj5u.com熱心網友回復：
- 對陣列進行排序
- 對于
xindex 處的元素l，對陣列進行二進制搜索以獲取陣列中最大整數的索引，即< k-x。設索引為r。 - 對于 where 的所有子集
min(subset) = x，我們可以有任何索引在 range 中的元素(l,r]。子集min(subset) = x的數量成為(r-l)元素的可能子集的總數，因此 count =2^(r-l)(或0ifr<l)。
（注意：在所有這些子集中，我們正在修復x。這就是為什么范圍(l,r]不包括l） - 您必須遍歷陣列，對每個元素/索引使用上述程序來獲取當前元素最小且子集滿足給定約束的子集的計數。如果找到帶有 的元素
count=0，則中斷迭代。
這應該具有0(N*log(N))復雜性，足以應付 imo 的面試問題。
對于給定的示例，排序陣列 = [2,4,5,7]。
- 對于元素
2和。計數= （覆寫l=0r=22^(2-0) = 4[2],[4,2],[2,5],[4,2,5] - 對于元素
4和。Count = ，然后我們中斷迭代。l=1r=00
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446401.html
標籤：算法
上一篇：調整二維矩陣大小的基本演算法