公司有一个检测系统,在单位时间内将每次检测结果保存。由于检测的环境受到外界干扰,会随机地出现异常值。以前的办法是:取得所有检测结果的最大值作为最终值。由于异常值的出现,导致检测结果非常不准确。于是思考在整个检测结果曲线中,取分布最密集的部分作为结果。(如果异常值大大多于正常值,且异常值的出现范围相同,则这种方法也不可靠。好在正常值是大多数)
算法实现的原理为:将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;
}
分享到:
相关推荐
给你一个 n 个节点的 无向带权连通 图,节点编号为 0 到 n - 1 ,再给你一个整数数组 edges ,其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。 部分边的边权为 -1(wi = -1),其他边的...
Java实现如下算法: 1.链表 ...时间复杂度O(n log n) 。 (6)堆排序 利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。
其中复杂度是数据结构与算法中最重要的概念 复杂度也叫渐进式复杂度,通常用大O来表示分为时间复杂度与空间复杂度,用来分析算法的执行效率与数据规模的增长关系。 分析复杂度的时候,低阶(n)、常量、系数三部分...
快速幂、快速乘算法 算法核心在于位运算,利用二进制位运算将O(n)的算法复杂度降到O(logn) 快速幂算法是一种优化的幂运算方法,它通过减少乘法的次数来加快计算速度。这种算法利用了幂运算的性质,特别是幂的...
二分法查找的时间复杂度为O(log n),其中n为数组长度。与顺序查找相比,二分法查找的时间复杂度更低,适用于大规模数据的查找。但是,二分法查找要求数组必须是有序的,如果数组无序,则需要先进行排序操作。 总之...
折半查找 折半查找(又称二分查找)是一种高效的...折半查找的时间复杂度为O(log n),其中n为数组长度。因此,折半查找比线性查找和冒泡排序等算法更高效。但是,折半查找要求数组必须是有序的,否则无法使用此算法。
归并排序是一种基于分治思想的排序算法,它将待排序的数组分成两部分,分别对这两部分递归地进行排序,最后将两个有序子数组合并成一个有序数组。它的时间复杂度为O(nlogn)。 归并排序的基本思路是将待排序的数组...
(2)在相同的规模 n下,复杂度O(n)的算法在时间上总是优于复杂度 O(2 n)的算法 (3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界 (4)同一个算法,实现语言的级别越高,执行效率就越低 A.(1) B...
排序思想:有一组数据待排序,排序区间为Array[0]~Array[n-1]。将数据分为有序数据和无序数据,第一次排序时默认Array[0]为有序数据,Array[1]~Array[n-1]为无序数据。有序数据分区的第一个元素位置为low,最后一个...
所以时间复杂度O(N^2) 传送门 --> 选择排序 外层从0开始默认outer是最小数的下标, 内存从outer+1位置开始遍历, 不稳定, 如{ 3, 3, 3, 2 }, 当比较最后一个4时, 是第一个3和2交换, 从而不稳定. 内外层遍历两次, ...
搜索插入位置可以通过二分查找算法来实现,时间复杂度为O(log n),其中n为数组长度。 搜索插入位置的具体步骤如下: 1. 将待查找区间的左边界设为0,右边界设为数组长度减1。 2. 计算待查找区间的中间位置mid,...
D. *建立函数create:根据一维数组a[n]建立一个单链表,使单链表中各元素的次序与a[n]中各元素的次序相同,要求该程序的时间复杂度为O(n)。 E. *整理函数tideup:在非递减有序的单链表中删除值相同的多余...
FSD字典存储数千万个字符串,连同一个数值(或任何其他固定长度的数据类型)强调最小化确定性有限状态自动机的增量 O(n) 构造,使用高度优化的稀疏表实现。 查找键 k 的复杂度为 O(|k|),与字典大小无关。 迭代给定...
集合中包含一组不重复出现且无特性顺序的元素。 HashSet的一些特性如下: 1、HashSet中的值不能重复且没有顺序。 2、HashSet的容量会按需自动添加。 构造方法: HashSet() 默认相等比较器创建一个空的新实例。 ...
(13) 设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为(B) 注:利用公式n=n0+n1+n2、n0=n2+1和完全二叉数的特点可求出 A. 349 B. 350 C. 255 D. 351 (14) 结构化程序设计主要强调的是(B) A.程序的规模 ...
算法的空间复杂度是指算法程序中指令(或语句)的条数 C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D. 以上三种描述都不对 (2) 以下数据结构中不属于线性数据结构的是______。(C) A. 队列 B. 线性表 C....
设有一组初始记录关键字序列(K1,K2,…,Kn),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki,右半部分的每个关键字均大于等于Ki。 void quickpass(int r[]...
性质4:具有n个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分。 3. 满二叉树与完全二叉树 满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在满二叉树中...
排序算法排序是指以递增/递增/不递减或递减/递减/不递增的顺序排列以下一组数字,我们在编程时需要某些算法才能实现。各种排序算法如下:气泡排序冒泡排序(有时也称为沉没排序)是一种简单的排序算法,它反复遍历要...
它是稳定的,具有一致的运行时间,并且空间复杂度为(O(n))。 快速排序:选择一个元素作为枢轴并对数组进行分区。 最差情况O(n)。 数据透视表的选择很重要,当数组较小时,它可以比合并排序更快。 由于其递归...