问题解决了,方法如下
///--从数组到----的方式
按理来说,这个问题应该是排序算法的弱问题。 这相当于仅将相等的元素放在一起/排序,而排序算法对所有元素进行排序。
后来想了想,这句话应该是错的,其实并不是一个弱问题……这个问题也可以理解为先找到重复元素,然后排序。 如果这样理解的话,这就成了一个很大的问题了……
我还没有想出nlogn方法,但我认为让排序算法快速的关键思想 - 并且不能解决问题
从 n 个元素的数组中删除重复元素表示为 T(n)
显然,T(n)=T(n/2)*2 + n^2/2。 这确实可以分而治之,但与排序算法不同的是,这里的公式是n^2/2。
之所以可以通过 和 来优化排序算法,主要是因为将其分解为子问题然后合成一个大问题的过程比较简单,因为将两个有序数组合成一个有序数非常简单。
然而,要将两个没有重复元素的数组合并为一个,仍然需要一一比较……
换句话说,这种删除 2 个小数组中重复元素的分而治之分解无法得到优化。
那么还有其他的优化方法吗? 我此刻没想到会这样。 。
堆排序之所以快,是因为它记录了比较的结果。
在排序算法中,这个数字的比较过程确实可以影响其他数字的比较。
那么在这个问题下,这个数字是否重复的比较过程对于其他数字的比较过程有用吗?
这根本没有用……真的,根本没有用。