Clasa a XII-a · Recapitulare pentru bacalaureatRead in English

Fișier — valorile comune a două șiruri ordonate în C++

În engleză: File: the common values of two sorted sequences

O(n)C++1770 de linii2 exemplefolosește date.in / date.out

Ideea

Cerința (tip subiectul III.3): fișierul date.in conține pe prima linie n și m (1 ≤ n, m ≤ 10^5), pe a doua linie n numere naturale ordonate crescător, iar pe a treia m numere naturale ordonate crescător (valori de cel mult 9 cifre, se pot repeta). Afișați valorile care apar în ambele șiruri, fiecare o singură dată, în ordine crescătoare, sau „nu exista”. Eficiența: nu căutăm fiecare element al primului șir în al doilea (n * m pași), ci folosim ideea interclasării: doi indici, câte unul în fiecare șir; îl avansăm pe cel cu valoarea mai mică, iar la egalitate afișăm valoarea și o sărim în ambele șiruri.

Descrierea în engleză

The task (exam part III.3 style): the file date.in holds n and m (1 ≤ n, m ≤ 10^5) on the first line, n natural numbers in increasing order on the second, and m natural numbers in increasing order on the third (values with at most 9 digits, repeats allowed). Print the values that appear in both sequences, each once, in increasing order, or 'nu exista' (none). Efficiency: we do not search the second sequence for every element of the first (n * m steps), but use the merging idea: two indices, one in each sequence; we advance the one with the smaller value, and on equality we print the value and skip it in both sequences.

Complexitate
O(n + m)
Clasa
Clasa a XII-a (Grade 12)

Exemple

Exemplul 1

Intrare (date.in)

6 5
1 3 3 5 8 10
2 3 3 8 11

Ieșire așteptată

3 8
Exemplul 2

Intrare (date.in)

2 2
1 2
3 4

Ieșire așteptată

nu exista

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

fisier-valori-comune-siruri-sortate.cpp
/*
 * Titlu: Fișier — valorile comune a două șiruri ordonate
 * Clasa: 12
 * Capitol: Recapitulare pentru bacalaureat
 * Descriere: Cerința (tip subiectul III.3): fișierul date.in conține pe prima
 *            linie n și m (1 ≤ n, m ≤ 10^5), pe a doua linie n numere naturale
 *            ordonate crescător, iar pe a treia m numere naturale ordonate
 *            crescător (valori de cel mult 9 cifre, se pot repeta). Afișați
 *            valorile care apar în ambele șiruri, fiecare o singură dată, în ordine
 *            crescătoare, sau „nu exista”. Eficiența: nu căutăm fiecare element al
 *            primului șir în al doilea (n * m pași), ci folosim ideea interclasării:
 *            doi indici, câte unul în fiecare șir; îl avansăm pe cel cu valoarea
 *            mai mică, iar la egalitate afișăm valoarea și o sărim în ambele șiruri.
 * Complexitate: O(n + m)
 *
 * Exemplu
 * Intrare:
 * 6 5
 * 1 3 3 5 8 10
 * 2 3 3 8 11
 * Ieșire: 3 8
 *
 * Exemplu
 * Intrare:
 * 2 2
 * 1 2
 * 3 4
 * Ieșire: nu exista
 */
#include <fstream>
#include <iostream>
using namespace std;

int a[100000], b[100000];

int main()
{
    ifstream fin("date.in");
    int n, m;
    fin >> n >> m;
    for (int i = 0; i < n; i++)
        fin >> a[i];
    for (int j = 0; j < m; j++)
        fin >> b[j];

    int i = 0, j = 0;
    bool gasit = false;
    while (i < n && j < m)
    {
        if (a[i] < b[j])
            i++;
        else if (a[i] > b[j])
            j++;
        else
        {
            int v = a[i];
            cout << v << ' ';
            gasit = true;
            while (i < n && a[i] == v)
                i++;
            while (j < m && b[j] == v)
                j++;
        }
    }
    if (!gasit)
        cout << "nu exista";
    cout << '\n';
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.