获得std :: set中间(中位数)的有效方法？

Question

std::set是一个排序树.它提供begin和end方法,所以我可以得到最小和最大,lower_bound并upper_bound用于二进制搜索.但是如果我想让迭代器指向中间元素(或者其中一个元素,如果有偶数个元素)怎么办？

有没有一种有效的方法(O(log(size))不O(size))这样做？

{1} => 1
{1,2} => 1 or 2
{1,2,3} => 2
{1,2,3,4} => 2 or 3 (but in the same direction from middle as for {1,2})
{1,312,10000,14000,152333} => 10000

PS:俄语同样的问题.

Answer 1

根据您插入/删除项目的频率而不是查找中间/中间值,可能比明显的解决方案更有效的解决方案是将持久性迭代器保留到中间元素,并在插入/删除集合中的项目时更新它.有一堆边缘情况需要处理(奇数与偶数项目,删除中间项目,空集等),但基本的想法是当你插入一个小于当前中间项目的项目,你的中间迭代器可能需要递减,而如果你插入一个更大的迭代器,你需要递增.这是删除的另一种方式.

在查找时,这当然是O(1),但它在每次插入/删除时也具有基本上O(1)的成本,即在N次插入之后的O(N),其需要在足够数量的查找中分摊.使其比暴力强迫更有效.

Answer 2

这个建议是纯魔法，如果有一些重复的项目就会失败

根据您插入/删除项目与查找中间/中位数的频率，一种可能比明显解决方案更有效的解决方案是保持中间元素的持久迭代器并在您从集合中插入/删除项目时更新它。有一堆边缘情况需要处理（奇数与偶数项、删除中间项、空集等），但基本思想是，当您插入一个小于当前中间项的项时，你的中间迭代器可能需要递减，而如果你插入一个更大的迭代器，你需要递增。移除的方式正好相反。

建议

1. 第一个建议是使用 std::multiset 而不是 std::set，这样当项目可以被复制时它可以很好地工作
2. 我的建议是使用 2 个 multisets 来跟踪较小的药水和较大的药水并平衡它们之间的大小

算法

1. 保持集合平衡，使 size_of_small==size_of_big 或 size_of_small + 1 == size_of_big

void balance(multiset<int> &small, multiset<int> &big)
{
    while (true)
    {
        int ssmall = small.size();
        int sbig = big.size();

        if (ssmall == sbig || ssmall + 1 == sbig) break; // OK

        if (ssmall < sbig)
        {
            // big to small
            auto v = big.begin();
            small.emplace(*v);
            big.erase(v);
        }
        else 
        {
            // small to big
            auto v = small.end();
            --v;
            big.emplace(*v);
            small.erase(v);
        }
    }
}

2.如果集合是平衡的，中项总是大集合中的第一项

auto medium = big.begin();
cout << *medium << endl;

3.添加新项目时要小心

auto v = big.begin();
if (v != big.end() && new_item > *v)
    big.emplace(new_item );
else
    small.emplace(new_item );

balance(small, big);

复杂性解释

• 找到中间值是 O(1)
• 添加一个新项目需要 O(log n)
• 你仍然可以在 O(log n) 中搜索一个项目，但你需要搜索 2 个集合

Answer 3

获得二元搜索树的中间部分将是O(大小).您可以std::advance()按如下方式获得:

std::set<int>::iterator it = s.begin();
std::advance(it, s.size() / 2);

Answer 4

请注意，std::set不存储重复值。如果插入以下值{1, 2, 3, 3, 3, 3, 3, 3, 3}，您将检索到的中位数是2。

std::set<int>::iterator it = s.begin();
std::advance(it, s.size() / 2);
int median = *it;

如果您想在考虑中位数时包含重复项，您可以使用std::multiset（{1, 2, 3, 3, 3, 3, 3, 3, 3}中位数是3）：

std::multiset<int>::iterator it = s.begin();
std::advance(it, s.size() / 2);
int median = *it;

如果您希望对数据进行排序的唯一原因是获得中位数，那么在我看来，您最好使用普通的旧std::vector+ 。std::sort

通过大量测试样本和多次迭代，我使用 和 在 5 秒内完成了测试std::vector，使用或std::sort则在 13 到 15 秒内完成了测试。您的里程可能会有所不同，具体取决于您拥有的重复值的大小和数量。std::setstd::multiset