Ofe*_*gen 5 arrays algorithm data-structures
给定一个n的大小数组,其中:1/2的数组具有单个(未知)值.阵列的1/4具有单个(未知)不同的值.等等为1/8,1/16,1/32给出一个算法来对数组进行排序.您不能使用查找中值算法
所以我想的是:只有logn不同的值有一个简单的解决方案在O(n*loglogn)上使用二进制堆它看起来像是一个需要在O(n)中解决的问题
这个想法是使用多数算法，该算法需要 O(n)，然后发现“一半”值是多少，将其从数组中删除，然后在新数组 n+n/2+n/4+n/8+ 上再次执行此操作..... < 2n => O(n)