16

给定一个大小为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]
4

7 回答 7

6

您当前的解决方案是O(NK^2)（假设K > log N）。通过一些分析，我相信您可以将其减少到O(NK).

最接近的大小为 K 的集合将由排序列表中相邻的元素组成。您本质上必须首先对数组进行排序，因此后续分析将假设每个K数字序列都已排序，从而可以简化双重求和。

假设数组是这样排序的，x[j] >= x[i]当 时j > i，我们可以重写您的接近度指标以消除绝对值：

在此处输入图像描述

接下来，我们将您的符号重写为具有简单边界的双重求和：

在此处输入图像描述

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]
于 2013-10-21T05:54:44.980 回答
2

itertools来救援？

from itertools import combinations

def closest_elements(iterable, K):
    N = set(iterable)
    assert(2 <= K <= len(N) <= 10**5)

    combs = lambda it, k: combinations(it, k)
    _abs = lambda it: abs(it[0] - it[1])
    d = {}
    v = 0

    for x in combs(N, K):
        for y in combs(x, 2):
            v += _abs(y)

        d[x] = v
        v = 0

    return min(d, key=d.get)

>>> a = [10,100,300,200,1000,20,30]
>>> b = [1,2,3,4,10,20,30,40,100,200]
>>> print closest_elements(a, 3); closest_elements(b, 4)
(10, 20, 30) (1, 2, 3, 4)
于 2013-10-20T21:29:54.537 回答
2

这个过程可以用O(N*K)ifA是 sorted 来完成。如果A未排序，则时间将受排序过程的限制。

这是基于 2 个事实（仅在A订购时相关）：

  • 最接近的子集将始终是后续的
  • 在计算K后续元素的接近度时，距离之和可以计算为每两个后续元素之和 time (K-i)*iwhere iis 1,...,K-1。
  • 当遍历排序后的数组时，重新计算整个总和是多余的，我们可以改为删除K乘以先前两个最小元素之间的距离，并加上K乘以两个新最大元素的距离。这个事实被用来O(1)通过使用前一个子集的接近度来计算一个子集的接近度。

这是伪代码

List<pair> FindClosestSubsets(int[] A, int K)
{
    List<pair> minList = new List<pair>;
    int minVal = infinity;
    int tempSum;
    int N = A.length;

    for (int i = K - 1; i < N; i++)
    {
        tempSum = 0;

        for (int j = i - K + 1; j <= i; j++)
              tempSum += (K-i)*i * (A[i] - A[i-1]);

        if (tempSum < minVal)
        {
              minVal = tempSum;
              minList.clear();
              minList.add(new pair(i-K, i);
        }

        else if (tempSum == minVal)
              minList.add(new pair(i-K, i);
    }

    return minList;
}

此函数将返回表示最佳解决方案的索引对列表（每个解决方案的开始和结束索引），这暗示了您要返回最小值的所有解决方案的问题。

于 2013-10-21T06:23:24.320 回答
1

尝试以下操作：

N = input()
K = input()
assert 2 <= N <= 10**5
assert 2 <= K <= N
a = some_unsorted_list
a.sort()

cur_diff = sum([abs(a[i] - a[i + 1]) for i in range(K - 1)])
min_diff = cur_diff
min_last_idx = K - 1
for last_idx in range(K,N):
    cur_diff = cur_diff - \
               abs(a[last_idx - K - 1] - a[last_idx - K] + \
               abs(a[last_idx] - a[last_idx - 1])
    if min_diff > cur_diff:
        min_diff = cur_diff
        min_last_idx = last_idx

从 min_last_idx，您可以计算 min_first_idx。我使用范围来保留 idx 的顺序。如果这是 python 2.7，它将线性地占用更多的 RAM。这与您使用的算法相同，但效率稍高（复杂度较小的常数），因为它比对所有的求和要少。

于 2013-10-20T20:35:41.470 回答
1

排序后，我们可以确定，如果 x1, x2, ... xk 是解，那么 x1, x2, ... xk 是连续元素，对吧？

所以，

  1. 取数字之间的间隔
  2. 对这些间隔求和以获得 k 个数字之间的间隔
  3. 选择其中最小的
于 2013-10-20T22:36:42.793 回答
0

我最初的解决方案是查看所有 K 元素窗口并将每个元素乘以 m 并取该范围内的总和，其中 m 由 -(K-1) 初始化并在每一步中递增 2 并从整个列表。因此，对于大小为 3 的窗口，m 为 -2，范围的值为 -2 0 2。这是因为我观察到了一个属性，即 K 窗口中的每个元素都为总和添加了一定的权重。例如，如果元素为 [10 20 30]，则总和为 (30-10) + (30-20) + (20-10)。因此，如果我们分解表达式，我们有 2*30 + 0*20 + (-2)*10。这可以在 O(n) 时间内实现，整个操作将在 O(NK) 时间内完成。然而事实证明，这个解决方案不是最优的，并且在某些边缘情况下这个算法会失败。我还没有弄清楚这些情况，

for(i = 0 ;i <= n - k;++i)
{
    diff = 0;
    l = -(k-1);
    for(j = i;j < i + k;++j)
    {
        diff += a[j]*l;
        if(min < diff)
            break;
        l += 2;
    }
    if(j == i + k && diff > 0)
    min = diff;
}
于 2013-10-22T04:26:33.410 回答
0

您可以O(n log n)通过滑动窗口方法来做到这一点（O(n)如果数组已经排序）。

首先，假设我们已经在数组中的每个索引处预先计算了从到前一个元素i的距离之和。那个公式是A[i]k-1

(A[i] - A[i-1]) + (A[i] - A[i-2]) + ... + (A[i] - A[i-k+1]).

如果i小于k-1，我们只计算数组边界的总和。

假设我们还在数组中的每个索引处预先计算从到下一个元素i的距离之和。然后我们可以通过单次滑动窗口来解决整个问题。A[i]k-1

如果我们的滑动窗口[L, L+k-1]以接近和打开S，那么间隔的接近和[L+1, L+k]就是S - dist_sum_to_next[L] + dist_sum_to_prev[L+k]。成对距离之和的唯一变化是在它离开我们的窗口时删除所有涉及的项，并在它进入我们的窗口A[L]时添加所有涉及的项。A[L+k]

剩下的唯一部分是如何在一个位置计算与前一个元素i之间的距离之和（另一个计算是完全对称的）。如果我们知道 处的距离总和，这很容易：减去到的距离，并加上从到次的额外距离A[i]k-1i-1A[i-1]A[i-k]A[i-1]A[i] k-1

dist_sum_to_prev[i] =   (dist_sum_to_prev[i - 1] - (A[i - 1] - A[i - k])
                      + (A[i] - A[i - 1]) * (k - 1)

Python代码：

def closest_subset(nums: List[int], k: int) -> List[int]:
    """Given a list of n (poss. unsorted and non-unique) integers nums,
     returns a (sorted) list of size k that minimizes the sum of pairwise
     distances between all elements in the list.

     Runs in O(n lg n) time, uses O(n) auxiliary space.
    """

    n = len(nums)
    assert len(nums) == n
    assert 2 <= k <= n

    nums.sort()

    # Sum of pairwise distances to the next (at most) k-1 elements
    dist_sum_to_next = [0] * n

    # Sum of pairwise distances to the last (at most) k-1 elements
    dist_sum_to_prev = [0] * n

    for i in range(1, n):
        if i >= k:
            dist_sum_to_prev[i] = ((dist_sum_to_prev[i - 1] -
                                    (nums[i - 1] - nums[i - k]))
                                   + (nums[i] - nums[i - 1]) * (k - 1))
        else:
            dist_sum_to_prev[i] = (dist_sum_to_prev[i - 1]
                                   + (nums[i] - nums[i - 1]) * i)

    for i in reversed(range(n - 1)):
        if i < n - k:
            dist_sum_to_next[i] = ((dist_sum_to_next[i + 1]
                                    - (nums[i + k] - nums[i + 1]))
                                   + (nums[i + 1] - nums[i]) * (k - 1))
        else:
            dist_sum_to_next[i] = (dist_sum_to_next[i + 1]
                                   + (nums[i + 1] - nums[i]) * (n-i-1))

    best_sum = math.inf
    curr_sum = 0
    answer_right_bound = 0

    for i in range(n):
        curr_sum += dist_sum_to_prev[i]
        if i >= k:
            curr_sum -= dist_sum_to_next[i - k]

        if curr_sum < best_sum and i >= k - 1:
            best_sum = curr_sum
            answer_right_bound = i

    return nums[answer_right_bound - k + 1:answer_right_bound + 1]
于 2022-02-06T06:18:35.763 回答