algorithm - 生成彼此相邻的数字组

Question

我正在寻找一种算法来解决以下问题:

我有一组数字

(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)

你怎么看？

Answer 1

这是我的第一张照片(来自评论)。当我有更好的想法时，我会编辑这篇文章。

算法:

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;
}