我有一个向量，其中元素与值成对且其出现次数（值是唯一的）。我想找到矢量分位数，就好像值是重复出现次数一样。关于运行时复杂性，最好的方法是什么？
例如。如果向量由3个元素（1,4），（2,5），（3,1）组成，则0.1位数为1，0.5位数为2，因为整个向量为1，1，1，1， 2 2 2 2 3
如果我创建带有重复元素的矢量，nth_element会做到这一点，但由于它需要大量内存，所以我不想这么做。
对于地图而不是矢量，我也有同样的问题，因为我可以将前者替换为后者。
最佳答案
观察到第Q个分位数，[0,1]中的Q是穿过完全展开的矢量（或映射，这没有区别）的所有元素的元素Q分数。
在O（n）时间中，您可以对计数求和，例如在您的示例中为10。然后将其乘以Q即可得到目标索引，因此对于Q = 0.5，您的target = 5。
现在，您可以在O（n）时间内再次扫描紧缩矢量的元素，对计数求和，直到达到目标索引（5）。在您的示例中，这将发生在（2，5）。这里的第一个值是答案。
关于c++ - 如何在c++中找到包含值及其出现的 vector 的分位数？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38426042/