algorithm - 检测几乎已排序的数组中的未排序元素

Question

我有一组已排序的样本，但由于数据中的错误，有时会出现未排序的值。我需要检测这些值并将其删除。我将在下面展示一些示例数据集。

20 30 21 22 23 24 25

30 31 21 22 23 24 25

30 21 22 23 24 25 26

20 21 22 23 18 25 26

20 15 21 22 23 24 25

在每种情况下，粗斜体数字都是应该删除的数字。删除这些数字/检测这些数字的索引的算法是什么？

Answer 1

检测相对简单，步骤较少 - 您可以在 O(n) 时间内完成。只需遍历数组并将每个元素与下一个元素进行比较。您将能够找到(并标记索引或丢弃)乱序的数字。

但是，您的第二种情况使这样做成为一个问题。我假设您总是希望保留数字列表中最长的递增子序列(如第二种情况)。

您可以使用数组和二分查找高效地解决这个问题。该算法对每个序列元素执行一次二分查找，其总时间可以表示为O(n log n)。

按顺序处理序列元素，维护目前找到的最长递增子序列。将序列值表示为 X[0]、X[1] 等。L 表示迄今为止找到的最长递增子序列的长度。

M[j] 存储最小值 X[k] 的索引 k 使得存在递增的子序列长度 j 在 k ≤ i 范围内以 X[k] 结束。 j ≤ k ≤ i 总是。 P[k] 将 X[k] 的前导索引存储在以 X[k] 结尾的最长递增子序列中/p>

序列 X[M[1]], X[M[2]], ..., X[M[L]] 在算法的所有点上始终是非递减的。

P = array of length N
M = array of length N + 1 // Using a 1 indexed array for ease of understanding

L = 0
for i in range 0 to N-1:
   // Binary search
   lo = 1
   hi = L
   while lo ≤ hi:
       mid = ceil((lo+hi)/2)
       if X[M[mid]] < X[i]:
           lo = mid+1
       else:
           hi = mid-1

newL = lo

P[i] = M[newL-1]
M[newL] = i

if newL > L:
    L = newL

S = array of length L
k = M[L]
for i in range L-1 to 0:
    S[i] = X[k]
    k = P[k]

return S

可以在 Wikipedia article 上找到伪代码为此。

如果您确实想保留列表中的乱序元素，只需使用插入排序对数组进行排序即可。