c++ - 如何找到包含值及其在 C++ 中出现的 vector 的分位数？

Question

我有一个 vector ，其中元素与值及其出现次数成对(值是唯一的)。我想找到 vector 分位数，就好像值被重复出现次数一样。就运行时复杂性而言，最好的方法是什么？

例如如果 vector 由3个元素组成(1,4)，(2,5)，(3,1)，那么0.1分位数为1，0.5分位数为2，因为整 vector 为 1, 1, 1, 1, 2, 2, 2, 2, 2, 3。

如果我创建包含重复元素的 vector ，nth_element 会执行此操作，但我不想这样做，因为它需要大量内存。

我对 map 而不是 vector 有同样的问题，因为我可以用前者替换后者。

Answer 1

请注意 [0,1] 中的第 Q 个分位数 Q 是通过完全展开 vector (或映射 - 这没有区别)的所有元素的方式的元素 Q 分数。

在 O(n) 时间内，您可以对计数求和，例如在你的例子中是 10。然后将其乘以 Q 以获得目标索引，因此对于 Q=0.5，您的目标=5。

现在，您可以在 O(n) 时间内再次扫描紧凑 vector 的元素，对计数求和，直到达到目标索引 (5)。在您的示例中，这将发生在 (2, 5)。这里的第一个值是答案。