查找具有最接近彼此的K个元素的子集

Question

给定一个大小为N的整数数组,如何有效地找到大小为K的子集,其中元素彼此最接近？

让子集(x1,x2,x3,... xk)的接近度定义为:

2 <= N <= 10^5

2 <= K <= N

约束:数组可能包含重复项,不保证排序.

我的强力解决方案对于大N来说非常慢,并且它不会检查是否有超过1个解决方案:

N = input()
K = input()
assert 2 <= N <= 10**5
assert 2 <= K <= N
a = []
for i in xrange(0, N):
    a.append(input())
a.sort()

minimum = sys.maxint
startindex = 0

for i in xrange(0,N-K+1):
    last = i + K
    tmp = 0
    for j in xrange(i, last):
        for l in xrange(j+1, last):
            tmp += abs(a[j]-a[l])
            if(tmp > minimum):
                break

    if(tmp < minimum):
        minimum = tmp
        startindex = i #end index = startindex + K?

例子:

N = 7
K = 3
array = [10,100,300,200,1000,20,30]
result = [10,20,30]

N = 10
K = 4
array = [1,2,3,4,10,20,30,40,100,200]
result = [1,2,3,4]

Answer 1

您当前的解决方案是O(NK^2)(假设K > log N).通过一些分析,我相信你可以减少这个O(NK).

最接近的大小K集将由排序列表中相邻的元素组成.您基本上必须首先对数组进行排序,因此后续分析将假设每个K数字序列都已排序,这样可以简化双和.

假设数组已排序,以便x[j] >= x[i]何时j > i,我们可以重写您的closeness度量以消除绝对值:

接下来,我们将您的符号重写为带有简单边界的双重求和:

请注意,我们可以重写之间的内部距离x[i]和x[j]作为第三求和:

在那里,我习惯于d[l]简化未来的记法:

请注意,这d[l]是列表中每个相邻元素之间的距离.查看固定的内部两个求和的结构i:

j=i+1         d[i]
j=i+2         d[i] + d[i+1]
j=i+3         d[i] + d[i+1] + d[i+2]
...
j=K=i+(K-i)   d[i] + d[i+1] + d[i+2] + ... + d[K-1]

注意内部两个求和的三角形结构.这允许我们根据相邻术语的距离将内部两个求和重写为单个求和:

total: (K-i)*d[i] + (K-i-1)*d[i+1] + ... + 2*d[K-2] + 1*d[K-1]

这减少了总和:

现在我们来看看这个双重求和的结构:

i=1     (K-1)*d[1] + (K-2)*d[2] + (K-3)*d[3] + ... + 2*d[K-2] + d[K-1]
i=2                  (K-2)*d[2] + (K-3)*d[3] + ... + 2*d[K-2] + d[K-1]
i=3                               (K-3)*d[3] + ... + 2*d[K-2] + d[K-1]
...
i=K-2                                                2*d[K-2] + d[K-1]
i=K-1                                                           d[K-1]

再次注意三角形图案.总和然后变成:

1*(K-1)*d[1] + 2*(K-2)*d[2] + 3*(K-3)*d[3] + ... + (K-2)*2*d[K-2] 
  + (K-1)*1*d[K-1]

或者,写为一个总和:

这种紧凑的相邻差异单一总和是更有效算法的基础:

1. 排序数组,顺序 O(N log N)
2. 计算每个相邻元素的差异,顺序 O(N)
3. 迭代每个N-K差异序列并计算上述总和,顺序O(NK)

请注意,第二步和第三步可以合并,但使用Python,您的里程可能会有所不同.

代码:

def closeness(diff,K):
  acc = 0.0
  for (i,v) in enumerate(diff):
    acc += (i+1)*(K-(i+1))*v
  return acc

def closest(a,K):
  a.sort()
  N = len(a)
  diff = [ a[i+1] - a[i] for i in xrange(N-1) ]

  min_ind = 0
  min_val = closeness(diff[0:K-1],K)

  for ind in xrange(1,N-K+1):
    cl = closeness(diff[ind:ind+K-1],K)
    if cl < min_val:
      min_ind = ind
      min_val = cl

  return a[min_ind:min_ind+K]