数组中最大的子集，使得最小和最大元素的距离小于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中的解决方案比通用算法更可取。

- ChiCubed

---

你应该使用自定义的后缀树。 - Mazdak

这些值总是整数吗？ - samgak

@samgak 不，它们不一定是整数。 - ChiCubed

@Kasramvd 如果你有时间，请写一个实现这个定制后缀树的答案，如果它证明比在这里介绍的任何其他算法都更优化，我将接受它作为正确答案。 - ChiCubed

Answer 1

我假设我们不能通过排序修改数组，并且我们需要找到最大连续子集，因此我的解决方案（使用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.input:[14,14,14,15,16,17,17]

2.输出结果：14 14 14 15 16 17 17

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遍历数组元素时，将打印首先出现在数组中的子集。

但是，如果我们需要在数组中查找最大子集，该子集可以是连续的，也可以不连续，则解决方案将不同。

- Kalpesh Dusane

---

你好@Kalpesh，子集不一定是连续的，你可以对数组进行排序。(排序的时间复杂度是算法复杂度的一部分，但需要考虑在内。) - ChiCubed

Answer 2

这似乎与您的“幼稚”方法非常相似，但它是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是无效的。

- samgak

---

这正是我一直在寻找的。看起来O(n)是最好的选择。 - ChiCubed

Answer 3

暴力破解方法：

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

尝试进行优化！（提示：内部循环不需要像这里一样运行那么多次）

- Nee

Answer 4

对于这个问题，一个效率低下的算法（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)

- L3viathan

---

非常好！ - Mark

亲爱的@L3viathan，我知道暴力方法，我已经在我的程序中进行了明确说明。然而，我在这里正在寻找一个优化的算法。抱歉我之前没有表达得更清楚。 - ChiCubed

Answer 5

一种快速的方法，复杂度为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])

- Cabu