如何统计有序序列中指定容差范围内的不同元素数量

因为输入序列已经完成升序排序，无需额外排序操作，仅需单次遍历即可完成统计，时间复杂度为O(n)：

• 若序列为空直接返回0；非空序列初始化计数器为1，取第一个元素作为初始基准值
• 从第二个元素开始遍历，每个元素和当前基准值做容差校验
• 如果当前元素与基准值的差值超出容差范围，计数器加1，同时将当前元素更新为新的基准值
• 遍历结束后计数器的值即为符合规则的唯一值总数

你提供的测试序列与容差判断方法如下：

var l = new List<double>() { 0, 0 + 1e-7, 0 + 2e-7, 1 - 1e-7, 1 };

static bool IsWithinTolerance(double x, double y)
{
    return Math.Abs(x - y) < 1e-6;
}

统计方法实现：

static int CountUniqueWithTolerance(List<double> sortedList, Func<double, double, bool> toleranceCheck)
{
    if (sortedList == null || sortedList.Count == 0)
        return 0;
    
    int uniqueCount = 1;
    double lastBaseValue = sortedList[0];
    
    for (int i = 1; i < sortedList.Count; i++)
    {
        if (!toleranceCheck(sortedList[i], lastBaseValue))
        {
            uniqueCount++;
            lastBaseValue = sortedList[i];
        }
    }
    return uniqueCount;
}

调用方法：

int result = CountUniqueWithTolerance(l, IsWithinTolerance);

最终result返回值为2，符合预期：前3个元素均在0的容差范围内，后2个元素均在1的容差范围内，合计2个符合规则的唯一值。

内容的提问来源于stack exchange，提问作者malat