陣列中最大的子集，使得最小和最大的元素分開小於K

Question

給定一個數組，我想查找元素的最大子集，使得子集的最小和最大元素小於或等於K分開。具體來說，我想要的是元素，而不僅僅是大小。如果有多個事件，則可以匹配任何事件。

例如，在數組[14,15,17,20,23]中，如果K爲3，則可能的最大子集爲[14,15,17]。如果將17替換爲16，也是一樣。還應該匹配多個元素，例如[14,14,14,15,16,17,17]。數組不一定是排序的，但它可能是排序它的一個很好的起點。元素不一定是整數，子集不一定在原始數組中連續 - 我只是想要發生最大的可能子集。

爲了更清楚地說明理想的結果，一個簡單的方法是首先對數組進行排序，迭代排序數組的每個元素，然後創建一個新數組，包含當前元素，該元素被擴展後包含每個元素當前元素< = K大於它。 （即在上面的第一個例子中，如果當前元素爲20，那麼該數組將被擴展爲[20,23]，然後停止，因爲數組的末尾已到達;如果當前元素爲15，則數組將被擴展到[15,17]，然後停止，因爲20比15大3以上）。然後這個數組與當前的最大值進行檢查，如果它更大，則將取代當前的最大值。當前的最大值是最大的子集。 （在最大子集是數組的情況下，這種方法的複雜度爲O（N^2）。）

我意識到這種天真的方法，並且這個問題是要求優化的算法。

雖然我可以使用一般算法運行，但Python中的解決方案更可取。

Answer 1

這看起來非常類似於你的「天真」的方法，但它是O（n）排除排序，所以我不認爲你可以改進你的方法很多。優化是使用索引和僅創建一個第二陣列一旦答案是已知的：

def largest_less_than_k_apart(a, k): 
    a.sort() 
    upper_index = lower_index = max_length = max_upper_index = max_lower_index = 0 
    while upper_index < len(a): 
     while a[lower_index] < a[upper_index] - k: 
      lower_index += 1 
     if upper_index - lower_index + 1 > max_length: 
      max_length = upper_index - lower_index + 1 
      max_upper_index, max_lower_index = upper_index, lower_index 
     upper_index += 1 
    return a[max_lower_index:max_upper_index + 1] 

a = [14,15,17,20,23] 
print largest_less_than_k_apart(a, 3); 

輸出：

[14, 15, 17] 

它存儲在upper_index一次通過排序後的數組，與當前索引以及儘可能落後的另一個索引lower_index，同時仍指向大於或等於K的值小於當前元素的值。該函數會跟蹤兩個索引儘可能相距多遠，並使用這些索引來拆分列表並返回子集。

重複的元素進行處理，因爲lower_index滯後儘可能（指向最早的一式兩份），而當upper_index指向給定的子集的最後一個副本指數的差異將是最大的。

對於k傳遞負值是無效的。

Answer 2

暴力方法：

arr = [14,14,14,15,16,17,17] 
max_difference = 3 
solution = [] 

for i, start in enumerate(arr): 
    tmp = [] 
    largest = start 
    smallest = start 
    for j, end in enumerate(arr[i:]): 
     if abs(end - largest) <= max_difference and abs(end - smallest) <= max_difference: 
      tmp.append(end) 
      if end > largest: 
       largest = end 
      if end < smallest: 
       smallest = end 
     else: 
      break 
    if len(tmp) > len(solution): 
     solution = tmp 

儘量優化吧！ （提示：內循環並不需要運行多次，因爲它在這裏所做的）

Answer 3

低效率的算法（爲O（n^2）），因爲這將是非常簡單的：

l = [14,15,17,20,23] 
s = max((list(filter(lambda x: start<=x<=start+3, l)) for start in l), key=len) 
print(s) 

Answer 4

一與複雜度爲O（n *的log（n））的排序和O（n）的搜索產業鏈最長快捷方式：

list_1 = [14, 15, 17, 20, 23] 

k = 3 

list_1.sort() 
list_len = len(list_1) 

min_idx = -1 
max_idx = -1 
idx1 = 0 
idx2 = 0 

while idx2 < list_len-1: 
    idx2 += 1 
    while list_1[idx2] - list_1[idx1] > k: 
     idx1 += 1 
    if idx2 - idx1 > max_idx - min_idx: 
     min_idx, max_idx = idx1, idx2 

print(list_1[min_idx:max_idx+1]) 

Answer 5

我認爲我們不能排序它 &修改陣列我們必須找出最大的缺點ecutive子集，所以我的解決方案（在Python 3.2）是：

arr = [14, 15, 17, 20, 23] 
k = 3 
f_start_index=0 
f_end_index =0 
length = len(arr) 
for i in range(length): 
    min_value = arr[i] 
    max_value = arr[i] 
    start_index = i 
    end_index = i 
    for j in range((i+1),length): 
     if (min_value != arr[j] and max_value != arr[j]) : 
      if (min_value > arr[j]) : 
       min_value = arr[j] 
      elif (max_value < arr[j]) : 
       max_value = arr[j] 
      if(max_value-min_value) > k : 
       break 
     end_index = j 
    if (end_index-start_index) > (f_end_index-f_start_index): 
     f_start_index = start_index 
     f_end_index = end_index 
    if(f_end_index-f_start_index>=(length-j+1)): # for optimization 
     break 
for i in range(f_start_index,f_end_index+1): 
    print(arr[i],end=" ") 

這不是最有效的解決方案，但它會完成您的工作。

測試針對：

1。輸入：[14, 15, 17, 20, 23]

1.輸出：14 15 17

2，輸入：[14,14,14,15,16,17,17]

2。輸出：

3.輸入：[23 ,20, 17 , 16 ,14]

3.輸出：17 16 14

4.input：[-2,-1,0,1,2,4]

4.輸出：-2 -1 0 1

對於輸入數4有兩個可能的答案

• -2 -1 0 1
• -1 0 1 2 但我的解決方案首先好像子集的長度是相同的，那麼當我們遍歷從位​​置0到數組長度的數組元素時，它將打印數組中第一個出現的子集-1

但如果我們必須找到在陣列可能會或可能不會是連續的最大的子集然後解決方案將是不同的。