我有一个由n未排序元组组成的数据集，这些元组表示数字(比如特定的颜色代码)及其频率(出现的次数)。
我想找到最坏情况复杂度为O(n)的数的确切中位数。
例如:
dataset: {(5000, 8000), (25000, 4000), (9, 9000)} median: 5000
dataset: {(7000, 4), (23000, 400), (3000, 9000), (2500, 12000), (19000, 350), (500, 9000)....} median: ?
尝试失败:
- "Decompress"列表(所以它看起来像这样:
{7000, 7000, 7000, 7000, 23000, 23000...})，然后排序。问题是-它需要Ω(nlogn)，可能更多，因为频率可以非常大，没有任何上限。 - 尝试在数据上使用快速选择。为了保证0 (n)时间复杂度，必须保证良好的枢轴选择。为此，我考虑了中位数的中位数(据说O(n))与数据-但我无法弄清楚如何在不解压的情况下做到这一点，从而使其可能超过O(n)。
是否有一种方法来操作元组列表，使它不会被解压缩，仍然使用中位数的中位数或另一种方法来找到中位数?
结束说明:我不想对数据集做任何假设——元组的数量，数字/频率的限制范围，等等)。
对值使用快速选择，并且在决定保留哪一半时只注意频率。
理想的枢轴是将列表值分成两半。因为这将使下一关的工作量减半。在整个数据集中发生的分裂并不特别。因为你的目标是把它降到你想要的一个值，然后你就完成了。
这意味着对于中位数的中位数，您可以在选择枢轴时完全忽略频率。然后，在决定保持支点的哪一边时，要注意频率。并在选择下一个枢轴时再次忽略频率。