时间戳

首页 > 解决方案 > 如何检查 O(N) 时间复杂度的多重集中是否有 2 个或多个具有相同值的元素？

c++ - 如何检查 O(N) 时间复杂度的多重集中是否有 2 个或多个具有相同值的元素？

问题描述

我有一个带有一些值的多集/任何容器，例如 {1,2,3,4,5,5} -> 这将返回一些值；{1,2,3,4,5} --> 将返回一些其他值；

我试图找出容器中是否有任何重复项，时间复杂度为 O(N)。

标签： c++

解决方案

由于std::multiset是有序容器，因此任何重复项都是连续的。该std::adjacent_find算法搜索连续相同的元素（线性复杂度）。

这是一个简单的布尔函数，用于测试重复int值。

#include <algorithm>

bool has_duplicates(const std::multiset<int> &mset)
{
    return std::adjacent_find(mset.begin(), mset.end()) != mset.end();
}

推荐阅读