将给定的整数数组转换为一个排序的数组，通过删除最少数量的元素来实现。

Question

我正在解决以下问题：

我需要通过删除最少数量的元素来将给定的整数数组转换为排序后的数组。

例如：[3,5,2,10,11] 通过删除 ‘2‘ 变成 [3,5,10,11] 即为排序后结果。或者 [3,6,2,4,5,7,7] 通过删除 ‘3‘,’6‘ 变成 [2,4,5,7,7] 或者删除 ‘6‘,’2‘ 后变成 [3,4,5,7,7] （这两种方法都移除了 2 个元素，所以它们都是正确的）。

我的想法是为每个元素保留一个计数器，以查看它与其他元素有多少个冲突。 我所说的冲突是：在第一个例子中，数字 '3' 和 '5' 分别与数字 '2' 发生了1次冲突，而数字 '2' 则与数字 '3' 和 '5' 发生了2次冲突。 因此，在计算冲突数组后，我从原始数组中删除具有最大冲突数的元素，并对剩余数组重复此操作，直到所有元素均没有冲突。

虽然这种方法不够高效（在某些情况下可能会产生错误的结果），所以我想知道是否有更好的解决方案。

- Lauro S.

---

这似乎是一道编程竞赛题目。是吗？ - amit

不是的（甚至不确定你的意思）。这只是我和我的团队在大学项目中的一小部分。 - Lauro S.

NP，并没有任何冒犯之意，只是想了解更多关于动机的信息，因为这可能会影响到可能的答案（例如更多/更少的教育性或更实用/不实用）。 - amit

没关系，我不会生气的。我想我正在寻找一个实用的答案，因为这是涉及编程项目的（我使用的工具并不重要，最让我困扰的是想法/算法）。 - Lauro S.

Answer 1

我认为这只是一个巧妙伪装的最长增长子序列问题版本。如果您删除最少数量的元素以获得排序序列，则剩下的就是原始数组的最长递增子序列。因此，您可以执行以下操作：

1. 找到最长递增子序列（存在O(n log n)算法），然后
2. 删除不在该子序列中的所有内容。

希望这有所帮助！

- templatetypedef

Answer 2

您可以基于数组中的元素构建DAG：

- 每个元素a[n]都是一个顶点。 - 对于任何一对元素(m,n)，其中(m < n)且(a[m] <= a[n])，添加有向边。 优化：您可以为已排序的子数组构建简单链。例如，如果a[m] <= a[m+1] <= a[m+2] <= a[m+3] > a[m+4]，则可以跳过为顶点m添加边(m,m+2)和(m,m+3)。

现在的目标是找到图中的最长路径，针对有向无环图有线性时间解决方案。

一种算法在上述维基百科页面和此处中有描述。

- Lior Kogan

---

这肯定能行，但请注意总体时间复杂度为O(n^2)，因为有向无环图中最长路径与边的数量成线性关系，而这些边的数量为O(n^2)。 - j_random_hacker

这个程序在O(n^2)时间内可以正确运行，但我认为有可能用O(n log n)的时间复杂度来解决它。 - templatetypedef

@templatetypedef：鉴于我的优化，我不确定它是否是O(n^2)。无论如何，你的解决方案更有效率。 - Lior Kogan

这是一个很酷的优化！但是，我认为如果你让数组在元素之间交替变大和变小，这仍然会产生O(n^2)的链接，但是常数因子会更低。 - templatetypedef

Answer 3

我会使用递归编程来完成它。这是我的伪代码：

/**
 *  sortedArray : an array already sorted.
 *  leftToSort : an unsorted array that need to be sorted/merged with sortedArray.
 *  first call to this function must be sortArrayByRemoval([], arrayToSort);
**/
public Integer[] sortArrayByRemoval(Integer[] sortedArray, Integer[] leftToSort){
    if(leftToSort.size==0){ 
        return sortedArray; //end of recursion
    }
    Integer candidate = leftToSort[0]; 
    if(candidate>=sortedArray[last]){ //append candidate to the sorted array
        return sortArrayByRemoval(sortedArray.append(candidate) , leftToSort.removeFirst());
    }else{
        //either we skip it
        Integer[] result1 = sortArrayByRemoval(sortedArray,leftToSort.removeFirst());
        //either we do back tracking
        Integer[] result2 = sortArrayByRemoval(sortedArray.removeLast(),leftToSort);
        //and finally we return the best choice (i.e. the longest array)
        return biggestArray(result1, result2);
    }
}

也许不是最高效的方法，但我认为它可以给出正确的答案。

- ben75

Answer 4

如果您不固执于从原始数组中字面上删除元素的想法，那么您需要的是原始数字序列的最长递增子序列。这是一个众所周知的经典问题，您可以在文献或教科书中找到许多例子。

（如果您坚持要删除，那么找到LCS并删除不在LCS中的所有内容。）

- Novak

---

被@templatetypedef抢先了。 - Novak