3

给定一个像[15, 14, 12, 3, 10, 4, 2, 1]. 如何确定哪些元素出现故障并删除它们（在本例中为数字 3）。我不想对列表进行排序，而是检测异常值并删除它们。

另一个例子：

[13, 12, 4, 9, 8, 6, 7, 3, 2]

我希望能够删除 #4 和 #7 以便我最终得到：

[13, 12, 9, 8, 6, 3, 2]

当您遇到这种情况时，还会出现一个问题：

[15, 13, 12, 7, 10, 5, 4, 3]

您可以删除 7 或 10 以使该数组排序。

一般来说，我要解决的问题是给出一个数字读数列表（有些可能会偏离很多）。我希望数组只包含遵循一般趋势线的值并删除任何异常值。我只是想知道是否有一种简单的方法可以做到这一点。

4

2 回答 2

3

higuaro 描述的一个简单算法可以帮助您生成正确的序列：

对于 index 处的每个元素i，如果a[i] < a[i + 1]我们可以简单地删除该元素a[i]。

for(int i = 0; i < size; i++)
    while(a[i] < a[i + 1]){
       remove a[i];
       i--;
    }

但是，这种方法不能保证移除元素的数量最少。例如，对于这个序列 [10, 9, 8, 100, 1, 0]，移除 100 将是最优的，而不是移除 8，然后是 9，然后是 10。

为了找到要删除的最小元素数，我们注意到我们需要找到最长的递减子序列，这类似于经典的最长递增子序列，其解决方案已在此处描述

于 2015-08-26T02:54:38.043 回答
3

我会将您的问题简化为最长的增加（减少）子序列问题。

https://en.wikipedia.org/wiki/Longest_increasing_subsequence

由于您的序列几乎已排序，因此保证您会收到满意的结果（即整齐地遵循趋势线）。

有很多解决方案；其中之一在Svetlin Nakov 和 Veselin Kolev的免费书籍“ C# 计算机编程基础”中有所描述；问题在第 257 页，练习 6 中提出；解决方案在第 260 页。

摘自书中：

编写一个程序，找出数组 arr[n] 中递增元素的最大序列。不必连续放置元素。例如：{9, 6, 2, 7, 4, 7, 6, 5, 8, 4} -> {2, 4, 6, 8}。

解决方案：

我们可以用两个嵌套循环和一个数组 len[0…n-1] 来解决这个问题。在数组 len[i] 中，我们可以保留最长的连续递增序列的长度，该序列从数组中的某个位置开始（确切位置无关紧要）并以元素 arr[i] 结束。因此 len[0]=1，len[x] 是最大和 max(1 + len[prev])，其中 prev < x 且 arr[prev] < arr[x]。按照定义，我们可以使用两个嵌套循环计算 len[0…n-1]：外部循环将使用循环变量 x 从左到右遍历数组。内部循环将从开始到位置 x-1 遍历数组并搜索最大值为 len[prev] 的元素 prev，其中 arr[prev] < arr[x]。搜索后，我们用 1 + len[prev] 的最大找到值来初始化 len[x]，如果没有找到这样的值，则使用 1。

所描述的算法找到所有最大升序序列的长度，这些序列在每个元素处结束。这些值中最大的一个是最长递增序列的长度。如果我们需要找到组成最长序列的元素本身，我们可以从序列结束的元素开始（在索引 x 处），我们可以打印它并搜索前一个元素（prev）。根据定义 prev < x 和 len[x] = 1 + len[prev] 所以我们可以通过从 1 到 x-1 的 for 循环找到 prev。之后，我们可以对 x=prev 重复相同的操作。通过多次查找和打印前一个元素（prev）直到它存在，我们可以找到组成最长序列的元素（从最后一个到第一个）。

于 2015-08-26T02:59:57.897 回答