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)

你怎么看？

4

1 回答 1

3

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

算法：

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;
}
于 2013-11-07T22:11:44.760 回答