阵列中最大的子集，使得最小和最大的元素分开小于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

但如果我们必须找到在阵列可能会或可能不会是连续的最大的子集然后解决方案将是不同的。