There are several arrays of names in a text file. It is necessary to separate and display the names that are in all arrays. The complexity of the program should not exceed Const*O(n log n) . n is the size of the array itself in the file ... The number of arrays in the file is random. The program must be written in C ++ .

What algorithm to use?

  • At least, what n is written ... - andy.37
  • one
    @ andy.37, read Computational complexity - LEQADA
  • @LEQADA, imagine reading. Do you understand what is n in this problem? General number of names? The number of arrays? The length of the largest array? Or, m. the number of inhabitants of Voronezh? - andy.37
  • n is the size of the array itself in the file ... I know what the complexity of the algorithm is. but I can’t find a taco algorithm - Aram
  • @ andy.37, well read and read. Well done. And what did I say that? - LEQADA

3 answers 3

Load the first array, put the items as keys in

 std::unordered_map<std::string, bool> m;

it will be approximately O (n).
The keys m are the names, the values ​​are false .

We read the elements of the next array, if the element is in m , set the value to true .

 auto it = m.find(x); if (it != m.end()) it->second = true;

Now, if the value in m is true , then the element was in both arrays. Remove from m all elements whose value is false .

Repeat for the rest of the arrays - read the elements, look for them in m , change the value. The second cycle removes unnecessary items.

  • Abyx and to understand this, what topics you need to know in c ++ - Aram
  • @Aram, containers, cycles. - Abyx
  • Abyx and when we read arrays in turn, arrays is not the second cycle? I can't say n ^ 2 anymore? - Aram
  1. We write arrays into one array in the form of pairs (Имя, Π½ΠΎΠΌΠ΅Ρ€ массива) , in the case of a large array - into a file.
  2. We apply to the resulting array (or file) a suitable sorting algorithm with complexity O (n log n) and the comparison operation Имя1 == Имя2 ? НомСр1 < НомСр2 : Имя1 < Имя2 Имя1 == Имя2 ? НомСр1 < НомСр2 : Имя1 < Имя2 . (The operation should be optimized so that there is one string comparison, not two)
  3. We filter the result by outputting only those names that have all the numbers in full. Since they will go in order, the complexity of this operation will not exceed n .

    It can be much faster. Use std::unordered_map<std::string, int> map Further pseudocode:

     for (int i=0; i<number_of_arrays; i++) { for (int j=0; j<array[i].size(); j++) { if (map.count(array[i][j])) { // провСряСм Π½Π°Π»ΠΈΡ‡ΠΈΠ΅ ΠΊΠ»ΡŽΡ‡Π° map[array[i][j]]++; // ΡƒΠ²Π΅Π»ΠΈΡ‡ΠΈΠ²Π°Π΅ΠΌ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅ счСтчика } else { map.emplace(array[i][j], 1); // добавляСм элСмСнт со счСтчиком 1 } } } // Из map ΠΎΡΡ‚Π°Π»ΠΎΡΡŒ Π²Ρ‹Π±Ρ€Π°Ρ‚ΡŒ ΠΊΠ»ΡŽΡ‡ΠΈ со счСтчиком Ρ€Π°Π²Π½Ρ‹ΠΌ number_of_arrays

    Two notes:

    1) works with non-repeating strings in arrays. It is easy to modify, one break for the outer loop.

    2) using map with unique keys will be faster

    3) complexity O (m n log (n)) - where m is the number of arrays, log (n) (EMNIP, but should no longer be) - the cost of finding the key in the map

    You need to know std :: string, std :: vector, std :: map (std :: unordered_map)

    • andy.37 and so does not exceed the complexity of the algorithm n log n? - Aram
    • Something seems to me that an algorithm with complexity that does not depend on the number of arrays will be very nontrivial, if possible at all. Amendment, rework for arrays with possibly repeated lines will not be so trivial. - andy.37
    • Okay .. thanks very much - Aram