c - 数组中具有相同顺序的序列 - 识别序列

Question

我正在寻找解决问题的提示:假设有一个数组，其中一些数字按升序排列，一些数字按降序排列，例如 [1,2,5,9,6,3,2,4,7,8] 的序列为 asc [1,2,5,9] , desc [(9),6,3,2], asc [(2),4,7,8]。

现在这不是问题，我可以简单地遍历一个数组并将它们添加到某个数据结构中，当方向改变时 - 我将这个结构存储在某个地方并开始填充下一个。

我发现棘手的是，如果我想要某种阈值。例如:[0,50,100,99,98,97,105,160]因此可以忽略按降序排列的序列 [(100), 99, 98, 97]，因为总体变化是 -3，而序列增加得更显着 (+100)，因此，算法只识别出一个升序排列。

我试过和上面相同的方法，简单地将所有序列添加到一个数据结构中，然后比较两个连续项的值变化:(100 vs -3 意味着 -3 可以忽略)。但问题是如果我说这种情况:

(仅示例从序列开始到结束的值变化)

[+100, -3, +1, -50]在这种情况下，我不能忽视下降运动，因为数字开始下降，然后略微上升，然后再次下降得非常明显。

它真的很容易被这样的东西搞糊涂:[+100, -3, +3, -3, +3, -50]

这是我想要实现的目标的快速草图: 黑线表示数组中的初始数据，红色细线是所需的结果输出

有人能指出我正确的方向吗？我将如何处理这种情况？一次比较多个序列慢慢地将序列组合在一起？也许我需要多次遍历序列？我不确定我是否遇到过这样的问题并且不知道工作算法。这是我在尝试分析一些数据时遇到的问题。

Answer 1

如果我理解正确的话，您希望您的曲线是一连串交替增加和减少的序列，并带有一些额外的噪音。

去除噪声的常用方法是过滤数据。有数百万种方法可以做到这一点，其中大多数都需要频率分析，但在您的情况下，您可能可以通过简单的操作获得足够好的结果。

要点是相关变量不是数组中的值，而是它们的变体。

给定 N 个值，考虑包含 N-1 个元素的数组，其中包含两个连续值之间的差值。

[0,50,100,99,98,97,105,160] -> 50,100,-1,-1,-1,6,45

现在消除所有绝对值低于给定阈值(例如 10)的值

-> 50,100,0,0,0,0,45

然后，您可以通过查看所有正值或空值的条纹来检测上升序列(考虑到零值或负值，对于下降序列也是如此)。

对于所有过滤过程，您必须为您的阈值找到一个最佳点。太低将无法消除无关紧要的变化，太高将消除明显的斜率反转。