找出元素之间距离最远的子集

Question

找出元素之间距离最远的子集

15

我有一个面试问题，但是我看不出来答案。给定大小为N的数组，找到大小为k的子集，其中子集中的元素彼此之间最远。换句话说，最大化元素之间最小的成对距离。

Example:

Array = [1,2,6,10]
k = 3

answer = [1,6,10]

暴力方法需要找到所有大小为 k 的子集，这在运行时是指数级的。

我想到的一个思路是从数组中均匀地取值。我的意思是：

1. 取第一个和最后一个元素 2. 找到它们之间的差异（在这种情况下为 10-1），并将其除以 k（（10-1）/3=3） 3. 从两端向内移动两个指针，选择距离上一个选定元素 +/-3 的元素。所以在这种情况下，您从 1 和 10 开始，找到最接近 4 和 7 的元素。那将是 6。

这基于这样的直觉，即元素应该尽可能均匀地分布。我不知道如何证明它是否有效。如果有人知道或有更好的算法，请分享。谢谢！

- citysushi

5个回答

2

基本思路是正确的。我认为你应该先对数组进行排序，然后取第一个和最后一个元素，然后确定剩下的元素。

我无法想出一个多项式算法来解决这个问题，所以我建议其中两种选择。

一种是使用搜索算法，分支限界风格，因为你手头有一个很好的启发式：任何解的上界都是迄今为止选定元素之间的最小间隔大小，所以第一次猜测（均匀间隔单元格，就像你建议的那样）可以给你一个很好的基线，这将有助于立即修剪大多数分支。这对于较小的 k 值的情况效果很好，尽管最坏情况的性能是 O(N^k)。

另一种选择是从相同的基线开始，计算它的最小成对距离，然后尝试改进它。假设你有一个最小距离为 10 的子集，现在尝试获取一个距离为 11 的子集。这可以通过贪心算法轻松完成——选择排序序列中的第一个项目，使其与前一个项目之间的距离大于或等于所需距离。如果成功，则尝试进一步增加，如果失败，则没有这样的子集。

当数组很大且 k 相对较大但数组中的元素相对较小时，后一种解决方案可能更快。如果它们受到某个值 M 的限制，则此算法将花费 O(N*M) 时间，或者通过小幅改进为 O(N*log(M))，其中 N 是数组的大小。

正如 Evgeny Kluev 在他的答案中建议的那样，最大成对距离也有一个很好的上界，可以在这些算法中使用。因此，后者的复杂度实际上是 O(N*log(M/k))。

- Qnan

1

您可以使用O(n*(log n) + n*log(M))完成此操作，其中M是max(A) - min(A)。

这个想法是使用二分搜索找到最大的可能间隔。

首先，对数组进行排序。然后，我们只需要一个辅助函数，它接受一个距离d，并贪心地构建尽可能长的子数组，其中连续元素之间至少相隔d。我们可以在O(n)时间内完成此操作。

如果生成的数组长度至少为k，则最大间隔可能为>=d。否则，它严格小于d。这意味着我们可以使用二分搜索来找到最大值。通过一些巧妙的方法，您可以缩小二分搜索的“低”和“高”边界，但排序已经变成了瓶颈。

Python代码:

def maximize_distance(nums: List[int], k: int) -> List[int]:
    """Given an array of numbers and size k, uses binary search
    to find a subset of size k with maximum min-pairwise-distance"""
    assert len(nums) >= k
    
    if k == 1:
        return [nums[0]]

    nums.sort()

    def longest_separated_array(desired_distance: int) -> List[int]:
        """Given a distance, returns a subarray of nums
        of length k with pairwise differences at least that distance (if
        one exists)."""

        answer = [nums[0]]

        for x in nums[1:]:

            if x - answer[-1] >= desired_distance:
                answer.append(x)

                if len(answer) == k:
                    break

        return answer

    low, high = 0, (nums[-1] - nums[0])

    while low < high:
        mid = (low + high + 1) // 2

        if len(longest_separated_array(mid)) == k:
            low = mid
        else:
            high = mid - 1

    return longest_separated_array(low)

- kcsquared

0

$length = length($array); sort($array); //将列表按升序排序 $differences = ($array << 1) - $array; //获取每个值与下一个最大值之间的差异 sort($differences); //将列表按升序排序 $max = ($array[$length-1]-$array[0])/$M; //这是结果可能达到的理论最大值 $result = array(); for ($i = 0; $i < $length-1; $i++){ $count += $differences[i]; if ($length-$i == $M - 1 || $count >= $max){ //如果不能再取更多硬币或超出了理论最大值，就添加一个点 $result.push_back($count); $count = 0; $M--; } } return min($result)

对于非代码人士：对列表进行排序，查找相邻两个元素之间的差异，将该列表进行排序（升序），然后循环遍历它，累加连续的值，直到要么超过理论最大值，要么剩余的元素不足；然后将该值添加到新数组中，并继续直到到达数组末尾。然后返回新创建的数组的最小值。

这只是一个快速的草稿。快速浏览一下，这里的任何操作都可以在线性时间内完成（排序使用基数排序）。

例如，对于1、4、7、100和200，M=3，我们得到：

$differences = 3, 3, 93, 100
$max = (200-1)/3 ~ 67
然后我们循环：
$count = 3, 3+3=6, 6+93=99 > 67 所以我们推入99
$count = 100 > 67 所以我们推入100
min(99,100) = 99

将其转换为集合解决方案是一个简单的练习，我留给读者（附注：在书中反复阅读之后，我一直想说这句话:P）。

- chacham15

0

我假设你的集合是有序的。如果不是，我的答案会稍微改变。

Let's suppose you have an array X = (X1, X2, ..., Xn)

Energy(Xi) = min(|X(i-1) - Xi|, |X(i+1) - Xi|), 1 < i <n

j <- 1
while j < n - k do
    X.Exclude(min(Energy(Xi)), 1 < i < n)
    j <- j + 1
    n <- n - 1
end while

- Lajos Arpad

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ElKamina · Accepted Answer

这可以使用DP在多项式时间内解决。

第一步是如您所提到的，对列表A进行排序。令X[i,j]表示从前i个元素A中选择j个元素的解决方案。

现在，X[i+1, j+1] = max( min( X[k,j], A[i+1]-A[k] ) )，其中k<=i。

初始化步骤和子集记忆化留给您自行处理。

在您的示例（1,2,6,10）中，它的工作方式如下：

    1    2   6   10
1   -    -   -    -
2   -    1   5    9
3   -    -   1    4
4   -    -   -    1