在几乎排序的数组中移除未排序/异常元素

Question

在几乎排序的数组中移除未排序/异常元素

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来使这个数组排序。通常，我要解决的问题是，给定一组数值读数（有些可能偏差很大），我希望数组只包括遵循总体趋势线的值，并删除任何异常值。我只是想知道是否有一种简单的方法来解决这个问题。

- ksloan

你能否删掉第一个满足条件的元素：a[i] < a[i + 1]？(O(n)) - higuaro

你想要删除最少数量的元素，还是任意数量都可以？ - Pham Trung

我喜欢那个想法 @higuaro，但是如果有多个异常元素，我该怎么做呢？ - ksloan

@PhamTrung 如果可能的话，请尽量减少。 - ksloan

2个回答

3

我会将你的问题简化为最长上升（下降）子序列问题。

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

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

有许多解决方案；其中一个在 Svetlin Nakov 和 Veselin Kolev 的免费书籍 "Fundamentals of Computer Programming with 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）开始，打印它并搜索前一个元素（prev）。根据定义，prev

- Igor Sowinski

我想这就是了！让我试试看。 - ksloan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pham Trung · Accepted Answer

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

对于每个索引处的元素 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。

为了找到要删除的最少元素数量，我们需要找到最长的下降子序列，这类似于经典的最长上升子序列，其解决方案已在此处描述。