14

我有一个面试问题，我似乎无法弄清楚。给定一个大小为 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. 从两端向内移动 2 个指针，从您之前的选择中挑选出 +/- 3 的元素。所以在这种情况下，你从 1 和 10 开始，找到最接近 4 和 7 的元素。那就是 6。

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

4

5 回答 5

7

这可以使用 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
于 2012-09-05T11:38:51.253 回答
2

我认为基本的想法是正确的。您应该首先对数组进行排序，然后取第一个和最后一个元素，然后确定其余元素。

我想不出一个多项式算法来解决这个问题，所以我会建议这两个选项之一。

一种是使用搜索算法，分支定界风格，因为您手头有一个很好的启发式方法：任何解决方案的上限都是到目前为止选择的元素之间间隙的最小大小，所以第一个猜测（均匀如您所建议的，间隔单元格）可以为您提供良好的基线，这将有助于立即修剪大部分分支。这适用于较小的值k，尽管最坏情况下的性能是O(N^k).

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

k后一种解决方案在数组较大且相对较大但数组中的元素相对较小的情况下会更快。如果它们受某个值 的约束M，则该算法将花费O(N*M)时间，或者稍有改进，O(N*log(M))，其中 N 是数组的大小。

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

于 2012-09-05T10:55:45.617 回答
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
于 2012-09-05T11:43:55.817 回答
0 
$长度=长度（$数组）；
排序（$数组）；//对列表进行升序排序
$differences = ($array << 1) - $array; //获取每个值与下一个最大值之间的差
排序（$差异）；//对列表进行升序排序
$max = ($array[$length-1]-$array[0])/$M; //这是结果可以有多大的理论最大值
$结果 = 数组（）；
for ($i = 0; i < $length-1; $i++){
    $count += $差异[i];
    if ($length-$i == $M - 1 || $count >= $max){ //如果没有更多的硬币可以拿，或者我们已经超过或等于理论最大值，添加一个观点
        $result.push_back($count);
        $计数 = 0;
        $M--;
    }
}
返回最小值（$结果）

对于非代码人员：对列表进行排序，找到每 2 个顺序元素之间的差异，对该列表进行排序（按升序），然后循环遍历它，总结顺序值，直到您通过理论最大值或没有足够的元素剩余; 然后将该值添加到一个新数组并继续，直到到达数组的末尾。然后返回新创建的数组的最小值。

不过，这只是一个快速草稿。一目了然，这里的任何操作都可以在线性时间内完成（排序的基数排序）。

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

$差异 = 3, 3, 93, 100
$max = (200-1)/3 ~ 67
然后我们循环：
$count = 3, 3+3=6, 6+93=99 > 67 所以我们推 99
$count = 100 > 67 所以我们推 100
最小（99,100）= 99

将其转换为我留给读者的设置解决方案是一个简单的练习（PS 在一直阅读一本书之后，我一直想说：P）

于 2012-09-08T08:12:56.737 回答
0

你可以做到这一点，O(n*(log n) + n*log(M))在哪里。Mmax(A) - min(A)

这个想法是使用二进制搜索来找到可能的最大分离。

首先，对数组进行排序。然后，我们只需要一个辅助函数，它接收一个 distance 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)
于 2022-02-06T06:54:24.910 回答