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

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"各自具有1间的冲突(用数字"2")和数字"2"已经2个冲突(带有号码"3"和"5") .因此,在计算冲突数组之后,我从原始数组中删除具有最大冲突数的元素,并且我重复其余数组,直到所有元素都有0个冲突.

这不是一种有效的方式(在某些情况下,我认为它也可能产生错误的结果),所以我想知道是否有人能想到更好的解决方案.

Answer 1

我相信这只是一个巧妙伪装的版本,是最长时间增长的子序列问题.如果删除具有已排序序列的最小元素数,则剩下的是原始数组中增长最长的子序列.因此,您可以执行以下操作:

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

希望这可以帮助!