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

Question

我有一个向量，其中元素与值及其出现次数成对（值是唯一的）。我想找到向量分位数，就好像值被重复出现次数一样。关于运行时间复杂度的最佳方法是什么？

例如如果vector由3个元素(1,4),(2,5),(3,1)组成，则0.1-quantile为1，0.5-quantile是2，因为整个向量是1, 1, 1, 1, 2, 2, 2, 2, 2, 3.

nth_element 如果我用重复的元素创建向量，我会这样做，但我不想这样做，因为它需要大量内存。

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

Answer 1

观察第 Q 分位数，Q 在 [0,1] 中，是通过完全扩展向量（或映射 - 这没有区别）的所有元素的方式的元素 Q 分数。

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

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

Answer 2

使用partial_sum和lower_bound可以找到对数顺序的分位数：

#include <iostream>
#include <iterator>
#include <map>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <iostream>
int main()
{
    std::vector<std::pair<int, int>> v {{1,4}, {2,5}, {3,1}};
    std::map<int,int> cum;
    std::swap(v.begin()->first, v.begin()->second);
    std::partial_sum(v.begin(), v.end(), std::inserter(cum, cum.begin()), 
        [](const std::pair<int,int>& a, const std::pair<int,int>& b)
        {
            return std::make_pair(a.first + b.second, b.first);
        }
    );
    std::swap(v.begin()->first, v.begin()->second);
    auto quantile = 0.1;
    std::cout << cum.lower_bound(quantile * cum.rbegin()->first)->second << std::endl;
    quantile = 0.5;
    std::cout << cum.lower_bound(quantile * cum.rbegin()->first)->second << std::endl;
    return 0;
}

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

How do I find quantile of vector which contain values and their occurrences in c++?

c++

vector

quantile