通过删除最小数量的元素，将给定的整数数组转换为排序的整数 [英] Convert a given array of integers to a sorted one, by deleting the minimum number of elements
问题描述
我正在解决以下问题：
我必须通过删除最小数量的元素，将给定的整数数组转换为排序后的整数。
I have to convert a given array of integers to a sorted one, by deleting the minimum number of elements.
例如：[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个元素，这就是它们都正确的原因）。
For example: [3,5,2,10,11] will be sorted by deleting ‘2‘ : [3,5,10,11]. Or [3,6,2,4,5,7,7] will be sorted by deleting ‘3‘,’6‘ : [2,4,5,7,7] OR by deleting ‘6‘,’2‘ : [3,4,5,7,7] (both ways i remove 2 elements, that’s why they are both correct).
我的想法是为每个元素保留一个计数器，以查看它与其他元素有多少冲突。
我的意思是冲突：在第一个示例中，数字 3和 5每个都有1个冲突（数字为 2），数字 2有2个冲突（数字为 3和'5'）。
因此，在计算了冲突数组之后，我从原始数组中删除了具有最大冲突数的元素，然后重复其余数组，直到所有元素的冲突都为0。
My thought was to keep a counter for each element to see how many conflicts it has with other elements. What i mean by conflicts: in the first example, numbers ‘3‘ and ‘5‘ have 1 conflict each (with the number ‘2‘) and number ‘2‘ has 2 conflicts (with numbers ‘3‘ and ‘5‘). So, after calculating the array of conflicts, i remove from the original array the element that has the max number of conflicts and i repeat for the remaining array until all elements have 0 conflicts.
虽然这不是一种有效的方法（在某些情况下，我还没有想到它可能还会产生错误的结果），所以我想知道是否有人可以想到更好的解决方案。
This is not an efficient way though (in some cases that i havent thought it might also produce wrong results), so i was wondering if anyone could think of a better solution.
推荐答案
我相信这只是 最长增长的子序列问题。如果删除具有排序序列的最小元素数，那么剩下的就是原始数组中最长的增长子序列。因此，您可以执行以下操作：
I believe this is just a cleverly disguised version of the longest increasing subsequence problem. If you delete the minimum number of elements to have a sorted sequence, what you're left with is the longest increasing subsequence of the original array. Accordingly, you can do the following:
- 找到最长的递增子序列（为此存在O（n log n）个算法），然后
- 删除该子序列中没有的所有内容。
希望这会有所帮助！
这篇关于通过删除最小数量的元素，将给定的整数数组转换为排序的整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
