There are two arrays (vectors, there is no difference what container to use) you need to find two elements that are in both the first and second. In addition to ideas about enumerating all the numbers, I did not invent anything.

You can of course use lower_bound for optimization.

But I need a quick response to the request (constant at best, because I can have a lot of arrays and also requests, about 1000 ).

How can this be done ? Perhaps there is some kind of algorithm that solves this problem.

  • Sorting + pass in search of matches. O (N lg N) due to sorting. If the same sorting is possible by counting - O (N). You can try to adjust the Bloom filter, of course, but then the element will not be known exactly + possible false positives. - Harry
  • For acceleration, you can connect multithreading. - MindCleaner
  • one
    Instead of sorting, you can dump an array into std: set or into std :: unordered_set, and go through the search for the second ... in fact is equivalent to the Harry sentence, but with the hash complexity will be close to O (N). - Fat-Zer
  • In order to talk about a multiple task, you need to know which part remains unchanged and which part changes. In any case, there can be no talk of a constant time. - AnT 4:34 pm

2 answers 2

vector<int> res; vector<int> fv{1, 4, 5, 9, 23, 12, 24, 45, 56, 75}; vector<int> sv {3, 6, 7, 23, 11, 12, 34, 46, 8, 19}; set_intersection(fv.begin(), fv.end(), sv.begin(), sv.end(), back_inserter(res)); // элементы вектора res

    Unfortunately I can not add comments. And std :: set_intersection does not help? If there are only two arrays, then calculating the intersection and putting it into a hash table (std :: unordered_set), for each query there will be almost O (N)

    • std::set_intersection requires input sorted arrays. - AnT pm
    • Right. But it seems to be written in the documentation, what are you talking about? If about O (N), then I had in mind the complexity of the query, excluding the pre-calculation (sorting of two arrays). And N is the size of the intersection, not the original arrays - vegorov
    • To the fact that in this problem the arrays are not ordered. Accordingly, in any solution that requires sorting, it is necessary to take into account the costs of sorting. - AnT