找出列表中有多少组

Question

我有一个列表，每个值都在 0..100 区间内。

例如：

[0,1,2,20,21,29,30,31,31,32,89,90,91,92,92,92,92]

是否有算法可以确定此列表中有多少组？对于上面的列表，应该说有 3 个组 (0..2), (20..32), (89..92).

据我所知，有一种 k-means 算法可以将列表分成一定数量的组，但就我而言，我需要首先确定有多少组，所以 k-意味着没有；这真的没有帮助。

如果语言有任何相关性，我将需要在 PHP 中执行此操作。

Answer 1

如果您知道您的组可以通过某个最小距离分开 d，您可以通过计算不在同一组中的所有连续元素来计算组：

Input: A, d
Output: num_groups

sort(A)
for i = 0 ... size(A) - 2
    if A[i + 1] - A[i] >= d
        num_groups++

如果您尚未确定最佳最小距离，最多有 k 个组，您可以通过计算 相邻差异 并选择k第大元素：

Input: A of size n, k
Output: d

sort(A)
adj_diff = array of n - 1 elements
for i = 0 ... n - 2
    adj_diff[i] = A[i + 1] - A[i]
sort(adj_diff)
d = adj_diff[n - 1 - k]
if d == adj_diff[n - 2 - k] // to make sure there are at most k groups,
    d++                     // otherwise we might have multiple groups
                            // with the same distance to their neighbors

找出列表中有多少组

find out how many groups are in a list

algorithm

grouping

k-means