我正在解决以下问题:
我必须通过删除最小数量的元素，将给定的整数数组转换为排序数组。
例如:[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。
虽然这不是一种有效的方法(在某些情况下我还没有想到它也可能产生错误的结果)，所以我想知道是否有人能想到更好的解决方案。
最佳答案
我相信这只是 longest increasing subsequence problem 的巧妙伪装版本. 如果您删除了具有排序序列的最小数量的元素，则剩下的是原始数组的最长递增子序列。因此，您可以执行以下操作:
- 找到最长的递增子序列(为此存在 O(n log n) 算法)，然后
- 删除不在该子序列中的所有内容。
希望这对您有所帮助!
关于arrays - 通过删除最小数量的元素，将给定的整数数组转换为排序数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13863373/