4

我正在解决以下问题：

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

例如：[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”各有 1 个冲突（数字“2”），数字“2”有 2 个冲突（数字“3”和“5”） . 因此，在计算冲突数组之后，我从原始数组中删除具有最大冲突数的元素，并对剩余的数组重复，直到所有元素都有 0 个冲突。

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

4

4 回答 4

7

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

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

希望这可以帮助！

于 2012-12-13T17:14:45.123 回答
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 +2) 和 (m,m+3) 用于顶点 m。

现在的目标是找到图中的最长路径，该路径对于有向无环图具有线性时间解。

上述 Wikipedia 页面和此处描述了一种算法。

于 2012-12-13T16:44:38.390 回答
0

我会用递归编程来做到这一点。这是我的伪代码：

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

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

于 2012-12-13T17:09:54.223 回答
0

如果您不坚持从原始数组中逐字删除内容的想法，那么您想要的是原始数字序列的最长递增子序列。这是一个众所周知的经典问题，您可以在文献或教科书中找到许多示例。

（如果你一直在删除，那么……找到 LCS 并删除所有不在 LCS 中的内容。）

于 2012-12-13T17:17:47.060 回答