c++ Нужно оптимизировать задачу

16 декабря 2021, 01:40

задания Yandex.Contest: Даны массив А и В. Нужно проверить, есть ли в массиве B элемент равный элементу массива А, если есть, то вывести Да Или Нет, если нету. Задачу выполнить удалось, но нужно ускорить время работы. Как я понял, там проводится 11 тестов, с каждым разом размеры увеличиваются. Дойдя до 9, не умещаюсь в рамки по времени. Может есть у кого предложения ?

include

using namespace std;
int main() {
    int N, K, m ,n;
    cin >> N;
    cin >> K;
    int *A = new int[N];
    int *B = new int[K];
    for (n = 0; n < N; n++) {
        cin >> A[n];
    }
    for (m = 0; m < K; m++) {
        cin >> B[m];
    }
    for (m = 0; m < K; m++) { // B
        for (n = 0; n < N; n++) { // A
            if (B[m] != A[n] && n == N - 1) {
                cout << "NO" << " ";
            }
            if (B[m] == A[n]) {
                cout << "YES" << " ";
                n = N;
            }
        }
    }
}

Answer 1

Решение данной задачи минимум штук 50)

Вот Вам 2 варианта просто на пересечение 2-х векторов

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> v1{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> v2{11, 2, 13, 14, 5, 16, 7, 8, 19, 20};
    std::sort(std::begin(v1), std::end(v1));
    std::sort(std::begin(v2), std::end(v2));
    std::vector<int> result;
    std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
    std::copy(std::begin(result), std::end(result), std::ostream_iterator<int>{std::cout, " "});
    return 0; 
}

Но так как это яндекс - лучше подумайте о решении через дерево, они такое любят))))

Вот вариант

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <unordered_set>

int main() {
    std::vector<int> v1{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> v2{11, 2, 13, 14, 5, 16, 7, 8, 19, 20};
    std::unordered_set<int> us(std::begin(v1), std::end(v1));
    for (auto v : v2) {
        if (us.find(v) != std::end(us)) {
            std::cout << v << std::endl;
        }
    }
    return 0; 
}

Ввод данных в вектор Вы должны организовать сами)