小编Muf*_*ous的帖子

想象一下，有一个整数数组，但不允许您访问任何值（因此不允许Arr[i] > Arr[i+1]或其他）。区分整数的唯一方法是使用query()函数：该函数将元素子集作为输入，并返回该子集中唯一整数的数量。目标是根据整数的值将它们分成组 \xe2\x80\x94 同一组中的整数应具有相同的值，而不同组中的整数应具有不同的值。\n问题 - 代码必须是 O( nlog(n))，或者换句话说，query() 函数只能被调用 O(nlog(n)) 次。

我花了几个小时在 Python 中优化不同的算法，但所有这些算法的复杂度都是 O(n^2)。作为参考，这是我开始的代码：

n = 100\nquerycalls = 0\nsecretarray = [random.randint(0, n-1) for i in range(n)]\ndef query(items):\n    global querycalls\n    querycalls += 1\n    return len(set(items))\ngroups = []\n

secretarray生成一个长度为 的巨大随机数字列表n。querycalls跟踪函数被调用的次数。groups是结果所在。

我做的第一件事是尝试创建一个基于合并排序的算法（将数组拆分，然后根据 query() 值合并），但我永远无法使其低于 O(n^2)。