通过删除最小数量的元素，将给定的整数数组转换为排序数组

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进行排序。

我的想法是为每个元素保留一个计数器，看看它与其他元素有多少冲突。我所说的冲突:在第一个例子中，数字“3”和“5”各有一个冲突(数字“2”)，数字“2”有2个冲突(数字“3”和“5”)。因此，在计算冲突数组后，我从原始数组中删除具有最大冲突数的元素，并对剩余的数组重复此操作，直到所有元素都有0个冲突。

虽然这不是一种有效的方法(在某些情况下，我没有想到它可能会产生错误的结果)，所以我想知道是否有人能想出更好的解决方案。

Answer 1

我相信这只是一个巧妙地伪装的.版本，如果你删除了排序序列的最小元素数，剩下的就是原始数组中最长的递增子序列。相应地，您可以执行以下操作：

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

希望这能有所帮助！

Answer 2

您可以基于阵列中的元素构建DAG：

对任意一对元素(m，n)，其中(m < n)和(am <= an)添加有向边。

优化:您可以为排序的子数组构建简单的链。例如，如果am<=a[m+1)<=am+2<=am+3>am+4，则可以跳过为顶点m添加边(m，m+2)和(m，m+3)。

现在的目标是找到longest path in the graph，它具有有向无环图的线性时间解决方案。

在前面提到的维基百科页面和here中描述了一个算法。

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);
    }
}

也许不是最有效的，但我认为它给了你正确的答案。