按顺序生成一组连续的数字

Question

按顺序生成一组连续的数字

algorithmlanguage-agnosticnumbersgrouping

3

我是一位有用的助手，可以为您翻译文本。

我正在寻找解决以下问题的算法：

我有一组数字。

(e.g 100,74,104,76,29,79,98,33,201)

我希望将相邻（差值为x）的数字分组。

例如，当x=10时，应输出：

[(100,104,98) (74,76,79) (33,29) (201)]

很不幸，我不知道如何做到这一点。

编辑：我有很多初始想法。算法不必高效，只要能工作就可以。

其中一个是：

- A) Picking first number, comparing its size with all the other numbers
- B) If the condition is complied, saving it in another set and deleting it from the input set
- C) Select the next element that isn't deleted and Start at A (Proceed until input set is empty)

你认为怎么样？

- tobawo

3

一种显而易见的方法是对列表进行排序，然后取出尽可能多的数字（即直到当前数字与第一个数字之间的距离超过“x”为止）。这将是“O(n log n)”的复杂度，可能过于复杂了。 - Alex Reinking

1

谢谢Alex！ @Doorknob：我在我的初始帖子中编辑了一个第一想法。 - tobawo

1

你可以考虑使用桶，例如对于每个差的倍数，你可以有一个桶。然后每个数字都被放置在最接近它的桶中（例如，在你的例子中，100、104和98将进入桶100，而76和79将进入桶70）。然后对于每个数字，它可以与其桶中的数字以及可能相邻两个桶中的数字分组。 - Rusty Rob

1

@AlexReinking 哎呀！我刚看到这个。不管怎样，除非数字在某种特定（小）整数范围内受限，否则我相信这是最有效的方法。 - RBarryYoung

1

@RBarryYoung 最好使用哈希表，这样只有在需要时才会创建桶 (因此最多只需要N个桶)。 - Rusty Rob

显示剩余10条评论

1个回答

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

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

- Alex Reinking · Accepted Answer

以下是我的第一次尝试（来自评论）。随着我得到更好的想法，我会编辑此帖子。

算法：

Input (a) a list L (b) a number x, the maximum gap
1) Sort the list
2) Take as many elements from the list as you can without exceeding the gap
3) Create a new group
4) If there are no more elements in the list, you're done, otherwise to to step 2.

例子：

Input:  L = [100,74,104,76,29,79,98,33,201], x = 10
Sorted: [29, 33, 74, 76, 79, 98, 100, 104, 201]
Output: [[29, 33], [74, 76, 79], [98, 100, 104], [201]]

既然我注意到您正在使用PHP，那么这里是PHP的一种实现：

function cluster($arr, $x)
{
        $clusters = array();
        if(count($arr) == 0)
                return $clusters;

        sort($arr);
        $curCluster[0] = array_shift($arr);
        while(count($arr) > 0) {
                $cur = array_shift($arr);
                if($cur - $curCluster[0] < $x)
                        array_push($curCluster, $cur);
                else {
                        array_push($clusters, $curCluster);
                        $curCluster = array($cur);
                }
        }
        if(count($curCluster) != 0)
                array_push($clusters, $curCluster);
        return $clusters;
}