复杂度为O(n)的取一组数中分布最密集的部分的算法

    公司有一个检测系统，在单位时间内将每次检测结果保存。由于检测的环境受到外界干扰，会随机地出现异常值。以前的办法是：取得所有检测结果的最大值作为最终值。由于异常值的出现，导致检测结果非常不准确。于是思考在整个检测结果曲线中，取分布最密集的部分作为结果。（如果异常值大大多于正常值，且异常值的出现范围相同，则这种方法也不可靠。好在正常值是大多数） 
    算法实现的原理为：将N个数排序，从第一个数开始累加，然后除以个数得到n个数以来平均值，把平均值和当前的数比较，如果范围超出一个阈值，则认为后面的数属于下一个段，然后重新从当前数开始累加比较。遍历完成后就可以把整段数据分成若干个段，段以内的数值的变化都是比较小的。
    在遍历中记录下每个段的长度，就可以得出数据最多的段，此段就是分布最密集的地方。把此段的值取平均就得到了检测中的正常值。
   算法的源码如下：

#include <stdio.h>
#include <string.h>

int Data[] = ...{2, 7, 8, 20, 23, 25, 26, 32, 37, 38, 44, 52, 67, 69, 69, 72, 81, 88, 88, 92};
//段的阈值，决定数值变化的大小
const int RANGE = 3;

void ShowSection(int Data[], int Count)  //显示数组中每个数据的分段结果
...{
    int* Sec = new int[Count];  //记录段的编号
    int nSum = 0;
    int nCount = 0;
    int nSection = 0;
    int nAvg;
    for (int i=0; i<Count; i++)
    ...{
        nSum += Data[i];
        nCount++;
        nAvg = nSum/nCount;  //取平均值
        if (!(nAvg+RANGE>=Data[i] && nAvg-RANGE<=Data[i]))  //如果当前值超过平均值的一定范围，则开始下一个段
        ...{
            nSum = Data[i];
            nCount = 1;
            nSection++;
        }
        Sec[i] = nSection;
    }
    //打印
    for (int i=0; i<Count; i++)
    ...{
        printf("%d %d ", Data[i], Sec[i]);
    }
    delete[] Sec;
    Sec = NULL;
}


//获得最大段的平均值
void ShowSection1(int Data[], int Count)
...{
    int nSum = 0;
    int nCount = 0;
    int nSection = 0;
    int nAvg;

    int nMaxSection = 0;  //最密集的段的ID
    int nMaxSectionCount = 0;  //最密集的段的元素个数
    int nResult = 0;  //计算后得出的平均值
    int nIndex = -1;  //段结束的下标
    for (int i=0; i<Count; i++)
    ...{
        nSum += Data[i];
        nCount++;
        nAvg = nSum/nCount;
        if (!(nAvg+RANGE>=Data[i] && nAvg-RANGE<=Data[i]))
        ...{
            if (nCount-1>nMaxSectionCount)  //如果当前段比上一个段还大，则当前段设置成最大段
            //如果存在多个数量相同的最大段，则使用大于取最后一个最大段，使用大于等于取第一个最大段
            ...{
                nMaxSectionCount = nCount -1;
                nMaxSection = nSection;
                nResult = (nSum - Data[i])/nMaxSectionCount;
                nIndex = i - 1;
            }
            nSum = Data[i];
            nCount = 1;
            nSection++;
        }
    }
    //打印和验证结果
    printf("nMaxSectionCount=%d ", nMaxSectionCount);
    printf("nMaxSection=%d ", nMaxSection);
    printf("nResult=%d ", nResult);
    nSum = 0;
    for (int i=nIndex-nMaxSectionCount+1; i<=nIndex; i++)
    ...{
        printf("data[%d]=%d ", i, Data[i]);
        nSum += Data[i];
    }
    printf("sum=%d, avg=%d ", nSum, nSum/nMaxSectionCount);
}

int main()
...{
    ShowSection(Data, 20);
    printf("=============================== ");
    ShowSection1(Data, 20);
    printf("=============================== ");
    return 1;
}