Блог

#c #vector #data-structures #set

#c #вектор #структуры данных #установить

Вопрос:

 #include<iostream>
#include<bits/stdc  .h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<int> v1(n);
        vector<int> v2(m);
        for (int i = 0; i < n; i  ) {
            cin >> v1[i];
        }
        for (int i = 0; i < m; i  ) {
            cin >> v2[i];
        }
        set<int> s1(v1.begin(),v1.end());
        set<int> s2(v2.begin(), v2.end());
        set<int> s3;
        set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(s3, s3.begin()));
        for (auto i : s3) cout << i;
    }
}
 

Комментарии:

1. set_union предполагает отсортированные массивы, что не гарантируется в вашем примере. с этим предположением это линейная сложность O (N M), где N и M — размеры массивов.

2. @StPiere На самом деле гарантируется, что это отсортированные массивы, поскольку это неупорядоченный набор, поэтому он сортируется автоматически при вставке (я не знаю, как, если вы тоже можете это объяснить). Итак, временная сложность этой строки set<int> s1(v1.begin(),v1.end()); линейна?? потому что то, что я прочитал вставки в наборе, взято O (logn), потому что это реализовано с помощью дерева RB.

3. ах, извините — наблюдал, что вы используете set. но просто идея: вы также можете работать с vector вместо set, если сначала отсортируете векторы

4. @StPiere Пожалуйста, прочтите отредактированный комментарий!! но если я использую vector, а затем сортирую, временная сложность будет O (nlogn)

5. Построение набора из вектора также имеет сложность N log (N) (если вектор еще не отсортирован — в противном случае устанавливается линейная сложность построения). В любом случае вы получаете общую сложность N log (N) для сортировки (напрямую или путем вставки в set), а затем линейную сложность для объединения.

Ответ №1: