找到最窄间隔的算法，其中m将包含一组数字

Let's say you have a list of n numbers. You are allowed to choose m integers (lets call the integer a). For each integer a, delete every number that is within the inclusive range [a - x, a + x], where x is a number. What is the minimum value of x that can get the list cleared?

假设你有一个n个数字的列表。允许选择m个整数(我们称其为整数a)。对于每个整数a，删除包含范围内的所有数字[a - x, a + x]，其中x是一个数字。可以清除列表的x的最小值是多少?

For example, if your list of numbers was

例如，如果你的数字列表是

1 3 8 10 18 20 25

1 3 8 10 18 20 25

and m = 2, the answer would be x = 5.

m = 2，答案是x = 5。

You could pick the two integers 5 and 20. This would clear the list because it deletes every number in between [5-5, 5+5] and [20-5, 20+5].

你可以选择两个整数5和20。这将清除列表，因为它删除[5- 5,5 +5]和[20- 5,20 +5]之间的所有数字。

How would I solve this? I think the solution may be related to dynamic programming. I do not want a brute force method solution.

我该怎么解决这个问题呢?我认为解决方案可能与动态规划有关。我不想要一个蛮力方法解决方案。

Code would be really helpful, preferably in Java or C++ or C.

代码将非常有用，最好是在Java或c++或C中。

5 个解决方案

#1

A recursive solution:

一个递归解决方案:

First, you need an estimation, you can split in m groups, then estimated(x) must be ~ (greather - lower element) / 2*m. the estimated(x) could be a solution. If there is a better solution, It has lower x than extimated(x) in all groups! and You can check it with the first group and then repeat recursively. The problem is decreasing until you have only a group: the last one, You know if your new solution is better or not, If there'is better, you can use it to discard another worse solution.

首先，您需要一个估计，您可以分割为m组，然后估计(x)必须是~ (greather - lower element) / 2*m。估计值(x)可以是一个解。如果有更好的解决方案，那么它在所有组中都比extimated(x)低x !你可以用第一组来检查然后递归地重复。问题是减少到只有一个组:最后一个，你知道如果你的新解决方案更好或者不更好，如果有更好的，你可以用它放弃另一个更糟糕的解决方案。

private static int estimate(int[] n, int m, int begin, int end) {    return (((n[end - 1] - n[begin]) / m) + 1 )/2;}private static int calculate(int[] n, int m, int begin, int end, int estimatedX){    if (m == 1){        return estimate(n, 1, begin, end);    } else {        int bestX = estimatedX;        for (int i = begin + 1; i <= end + 1 - m; i++) {            // It split the problem:            int firstGroupX = estimate(n, 1, begin, i);            if (firstGroupX < bestX){                bestX = Math.min(bestX, Math.max(firstGroupX, calculate(n, m-1, i, end, bestX)));            } else {                i = end;            }        }        return bestX;    }}public static void main(String[] args) {    int[] n = {1, 3, 8, 10, 18, 20, 25};    int m = 2;    Arrays.sort(n);    System.out.println(calculate(n, m, 0, n.length, estimate(n, m, 0, n.length)));}

EDIT:

编辑:

Long numbers version: Main idea, It search for "islands" of distances and split the problem into different islands. like divide and conquer, It distribute 'm' into islands.

长数字版本:主要思想，它搜索“岛屿”的距离，并把问题分成不同的岛屿。就像分治和征服一样，它把“m”分成了几个岛屿。

private static long estimate(long[] n, long m, int begin, int end) {    return (((n[end - 1] - n[begin]) / m) + 1) / 2;}private static long calculate(long[] n, long m, int begin, int end, long estimatedX) {    if (m == 1) {        return estimate(n, 1, begin, end);    } else {        long bestX = estimatedX;        for (int i = begin + 1; i <= end + 1 - m; i++) {            long firstGroupX = estimate(n, 1, begin, i);            if (firstGroupX < bestX) {                bestX = Math.min(bestX, Math.max(firstGroupX, calculate(n, m - 1, i, end, bestX)));            } else {                i = end;            }        }        return bestX;    }}private static long solver(long[] n, long m,  int begin, int end) {    long estimate = estimate(n, m, begin, end);    PriorityQueue<long[]> islands = new PriorityQueue<>((p0, p1) -> Long.compare(p1[0], p0[0]));    int islandBegin = begin;    for (int i = islandBegin; i < end -1; i++) {        if (n[i + 1] - n[i] > estimate) {            long estimatedIsland = estimate(n, 1, islandBegin, i+1);            islands.add(new long[]{estimatedIsland, islandBegin, i, 1});            islandBegin = i+1;        }    }    long estimatedIsland = estimate(n, 1, islandBegin, end);    islands.add(new long[]{estimatedIsland, islandBegin, end, 1});    long result;    if (islands.isEmpty() || m < islands.size()) {        result = calculate(n, m, begin, end, estimate);    } else {            long mFree = m - islands.size();        while (mFree > 0) {            long[] island = islands.poll();            island[3]++;            island[0] = solver(n, island[3], (int) island[1], (int) island[2]);            islands.add(island);            mFree--;        }        result = islands.poll()[0];    }    return result;}public static void main(String[] args) {    long[] n = new long[63];    for (int i = 1; i < n.length; i++) {        n[i] = 2*n[i-1]+1;    }    long m = 32;    Arrays.sort(n);    System.out.println(solver(n, m, 0, n.length));}

#2

Hints

Suppose you had the list

假设你有这个列表

1 3 8 10 18 20 25

and wanted to find how many groups would be needed to cover the set if x was equal to 2.

想知道如果x = 2需要多少组才能覆盖这个集合。

You could solve this in a greedy way by choosing the first integer to be 1+x (1 is the smallest number in the list). This would cover all elements up to 1+x+x=5. Then simply repeat this process until all numbers are covered.

你可以通过选择第一个整数为1+x(1是列表中最小的数)来贪婪地解决这个问题。这将覆盖1+x+x=5的所有元素。然后简单地重复这个过程，直到所有的数字都被覆盖。

So in this case, the next uncovered number is 8, so we would choose 8+x=10 and cover all numbers up to 10+x=12 in the second group.

在这种情况下，下一个未揭示的数是8，所以我们选择8+x=10，然后在第二组中涵盖所有的数，直到10+x=12。

Similarly, the third group would cover [18,24] and the fourth group would cover [25,29].

同样，第三组将覆盖[18,24]，第四组将覆盖[25,29]。

This value of x needed 4 groups. This is too many, so we need to increase x and try again.

x的这个值需要4组。这太多了，我们需要增加x，再试一次。

You can use bisection to identify the smallest value of x that does cover all the numbers in m groups.

可以使用二分法来确定x的最小值，该值确实包含m组中的所有数字。

#3

An effective algorithm can be(assuming list is sorted) ->

一个有效的算法可以是(假设列表已排序)->

1. We can think of list as groups of 'm' integers.

   我们可以把list看成是m个整数的组。

2. Now for each group calculate 'last_element - first_element+1', and store maximum of this value in a variable say, 'ans'.

   现在，对于每个组计算“last_element - first_element+1”，并将该值的最大值存储在一个变量中，比如“ans”。

3. Now the value of 'x' is 'ans/2'.

   现在x的值是ans/2。

I hope its pretty clear how this algorithm works.

我希望这个算法的工作原理很清楚。

#4

I think it's similarly problem of clusterization. For example You may use k-means clustering algorithm: do partitions of initial list on m classes and for x get maximum size divided by two of obtained classes.

我认为这也是一个类似的问题。例如，您可以使用k-means聚类算法:在m类上执行初始列表的分区，对x执行最大大小除以两个已获得的类。

#5

1) You should look into BEST CASE, AVERAGE CASE and WORST CASE complexities with regards to TIME and SPACE complexities of algorithms.

1)在算法的时间和空间复杂性方面，应该考虑最佳情况、平均情况和最差情况的复杂性。

2) I think David Pérez Cabrera has the right idea. Let's assume average case (as in the following pseudo code)

我认为大卫·佩雷斯·卡布雷拉的想法是对的。让我们假设平均情况(如下面的伪代码所示)

3) Let the list of integers be denoted by l

3)让整数列表用l表示

    keepGoing = true    min_x = ceiling(l[size-1]-l[0])/(2m)    while(keepGoing)    {        l2 = l.copy        min_x = min_x-1        mcounter = 1        while(mcounter <= m)        {            firstElement = l2[0]//  This while condition will likely result in an ArrayOutOfBoundsException//  It's easy to fix this.            while(l2[0] <= firstElement+2*min_x)            {   remove(l2[0])   }            mcounter = mcounter+1        }        if(l2.size>0)            keepGoing = false    }    return min_x+1

4) Consider

4)考虑

l = {1, 2, 3, 4, 5, 6, 7}, m=2 (gives x=2)l = {1, 10, 100, 1000, 10000, 100000, 1000000}, m=2l = {1, 10, 100, 1000, 10000, 100000, 1000000}, m=3