Как сделать левое соединение с векторным алгоритмом STL и алгоритмами STL со сложностью по времени лучше, чем O (n ^ 2)?

Question

У меня есть 2 вектора, которые содержат, скажем, объекты Person (имя, фамилия и т. Д.).Я хочу взять один из векторов (назовем его «большой»), затем для каждого элемента в этом векторе найти соответствующий элемент во втором («маленький») и объединить некоторые данные из «малого» векторного элемента в «большой» векторэлемент.Эта операция очень похожа на левое соединение в терминах SQL, но с дополнительным слиянием данных.Самый простой способ - сделать 2 цикла, но это приведет к O (n ^ 2) временной сложности.Могу ли я сделать лучше с алгоритмами STL?

Answer 1

Если вы сортируете маленький вектор, вы можете затем получить O (n log n) для части слияния, отсканировав большой вектор и используя binary_search , чтобы найти элементы в маленькомвектор.

Answer 2

Если ваши списки меняются не часто, вы можете отсортировать оба списка, а затем выполнить слияние по линейному времени, просто пройдя оба списка.

Если ваши списки меняют всеВозможно, вам лучше отсортировать «маленький» контейнер, такой как map или set.В этом случае просто используйте find в наборе для каждого элемента в большом списке, к которому вы хотите присоединиться.

Answer 3

Да!Вы можете сделать это в O (Nlogn) время сложности.Сортировать второй вектор, который занимает O (nlogn) время.для каждого элемента в первом векторе найдите соответствующий элемент во втором с помощью бинарного поиска (STL имеет алгоритм binary_search) и объедините данные с элементом в первом векторе.для каждого элемента в первом векторе мы тратим O (logn) время.Таким образом, сложность времени выполнения этого подхода составляет O (nlogn).