在 n 个可能的不同位置找到 k 个对象之间的最大最小距离？

Question

找到 n 个可能不同位置的 k 个对象之间的最大最小距离的有效方法是什么？

例如：

N：不同位置的数量比方说 N = 5 5个位置是{1,2,4,8,9}

K：假设 k = 3 的对象数

所以可能的答案（最大最小距离）将是：如果我们将对象放在 {1,4,8} 或 {1,4,9}

Answer 1

让我们对答案进行二分查找。
对于固定答案x，我们可以使用简单的线性贪心算法检查它是否可行（选择第一个元素然后遍历数组的其余部分添加当前元素，如果它与最后拾取的元素之间的距离大于或等于 x）。最后，我们只需要检查选择的元素数量至少为k。

时间复杂度为O(n * log MAX_A)，其中MAX_A为数组的最大元素。

这是该算法的伪代码：

def isFeasible(positions, dist, k):
    taken = 1
    last = positions[0]
    for i = 1 ... positions.size() - 1:
        if positions[i] - last >= dist:
            taken++
            last = positions[i]
    return taken >= k

def solve(positions, k):
    low = 0 // definitely small enough
    high = maxElement(positions) - minElement(positions) + 1 // definitely too big
    while high - low > 1:
        mid = (low + high) / 2
        if isFeasible(positions, mid, k):
            low = mid
        else:
            high = mid
    return low

在 n 个可能的不同位置找到 k 个对象之间的最大最小距离？

Finding largest minimum distance among k objects in n possible distinct positions?

algorithm