发现在N个可能的独特位置k个对象中最大的最小距离？ [英] Finding largest minimum distance among k objects in n possible distinct positions?

问题描述

这是一种有效的方法，以找到在n个可能的独特位置k个对象之中最大的最小距离是多少？

有关，例如：

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

K：对象的数量让说K = 3

因此​​，可能的答案（最大最小距离）将是：3如果我们把对象为{1,4,8}或{1,4,9}

解决方案

1. 让我们做了回答二进制搜索。

2. 对于一个固定的答案 X ，我们可以检查它是否是可行的，或不使用一个简单的线性贪心算法（选择第一个元素，然后遍历阵列将当前元素是否和最后拾取的元件之间的距离大于或等于的其余 X ）。最后，我们只需要检查采摘元素的数量至少为 K 。

时间复杂度为 O（N *登录MAX_A），其中 MAX_A 是数组的最大元素。

下面是一个伪code这个算法：

 高清isFeasible（位置，DIST，K）：
    取= 1
    最后=位置[0]
    对于i = 1 ... positions.size（） -  1：
        如果位置[I]  - 最后＆GT; = DIST：
            采取++
            最后=位置[I]
    返回拍摄＆GT; = K

高清解决（位置，K）：
    低= 0 //绝对够小
    高= maxElement（位置） -  minElement（位置）+ 1 //肯定过大
    而高 - 低＆GT; 1：
        中期=（低+高）/ 2
        如果isFeasible（位置，中，K）：
            低=中
        其他：
            高=中
    回报低
 

What is an efficient way to find largest minimum distance among k objects in n possible distinct positions?

For eg:

N: Number of distinct positions Lets say N = 5 and the 5 positions are {1,2,4,8,9}

K: Number of objects let say k = 3

So the possible answer (Largest Minimum Distance) would be: 3 if we put objects at {1,4,8} or {1,4,9}

解决方案

1. Let's do a binary search over the answer.

2. For a fixed answer x, we can check whether it is feasible or not using a simple linear greedy algorithm(pick the first element and then iterate over the rest of the array adding the current element if the distance between it and the last picked element is greater than or equal to x). In the end, we just need to check that the number of picked elements is at least k.

The time complexity is O(n * log MAX_A), where MAX_A is the maximum element of the array.

Here is a pseudo code for this algorithm:

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个对象中最大的最小距离？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！