假设一个实数数组 A[],不能直接通过 A[i]的方式查看数组中的目标值。
现在我们可以调用一个Q()的函数来得到一个数组中非重复数字的个数。比如
T = {1, 2, 2} Q(T) = 2
问题:如何在O(nlogn)次调用函数Q()的复杂度下,找到所有的重复数,并且把数组分类。相同的数放在一起,不同的数不放在一起。
*注意:整个程序的时间复杂度不在意,主要Q() 的调用满足O(nlogn)就可以。不需要完整代码,大纲和主要步骤即可。感谢!
e.g.
input: A[] = {1, 2, 1, 2, 1, 2}
output: {1, 1, 1, 2, 2, 2} or {1, 1, 1} {2, 2, 2} or 其他数据结构来达到相似效果
O(nlogn),明显是让你用hashtable的方法。
https://blog.csdn.net/wangdongli_1993/article/details/82149094