Cele mai mari două valori distincte în C++

În vectorul 7 7 3 5, cele mai mari două valori distincte sunt 7 și 5. Două poziții diferite nu garantează două valori diferite. Această precizare schimbă condițiile algoritmului și face insuficientă simpla alegere a ultimelor două elemente sortate.

Date și rezultat

Citim 1 ≤ n ≤ 1000 și n numere întregi între -10^9 și 10^9. Afișăm maximul și al doilea maxim distinct, în ordine descrescătoare. Dacă toate valorile sunt egale, afișăm NU EXISTA. Vectorul clasic are capacitatea 1000, dar folosim numai primele n poziții, de la 0 la n-1.

În 7, 7, 3, 5, cele două maxime distincte sunt 7 și 5, nu 7 și 7.Mărește schema ↗

Două valori și un indicator

prim este maximul prefixului citit. secund are sens numai când existaSecund este adevărat. Nu folosim zero ca semnal pentru absență, deoarece zero poate fi o valoare validă, iar toate datele pot fi negative.

Dacă apare un nou maxim, vechiul maxim devine al doilea. Dacă valoarea este egală cu maximul, o ignorăm. Dacă este mai mică, o comparăm cu al doilea maxim sau o folosim pentru a-l inițializa.

Pe -4 -4 -9 -2, după primele două poziții avem doar maximul -4. La -9 apare al doilea maxim. La -2, vechiul maxim -4 coboară pe locul al doilea. Răspunsul este -2 -4.

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int a[1000];
    for (int i = 0; i < n; ++i) cin >> a[i];
    int prim = a[0], secund = 0;
    bool existaSecund = false;
    for (int i = 1; i < n; ++i) {
        int x = a[i];
        if (x > prim) {
            secund = prim; existaSecund = true; prim = x;
        } else if (x < prim && (!existaSecund || x > secund)) {
            secund = x; existaSecund = true;
        }
    }
    if (existaSecund) cout << prim << ' ' << secund << '\n';
    else cout << "NU EXISTA\n";
}

Varianta echivalentă cu std::vector

Indicii și datele de intrare rămân aceleași. Containerul este construit cu numărul de elemente folosite; accesul prin [] cere în continuare indici valizi.

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int prim = a[0], secund = 0;
    bool existaSecund = false;
    for (int i = 1; i < n; ++i) {
        int x = a[i];
        if (x > prim) {
            secund = prim; existaSecund = true; prim = x;
        } else if (x < prim && (!existaSecund || x > secund)) {
            secund = x; existaSecund = true;
        }
    }
    if (existaSecund) cout << prim << ' ' << secund << '\n';
    else cout << "NU EXISTA\n";
}

Corectitudine și cost

După fiecare element, păstrăm cele mai mari două valori distincte din prefixul procesat, dacă există două. Cele trei cazuri de actualizare acoperă toate relațiile dintre noua valoare și maxim. Un duplicat al maximului nu poate înlocui al doilea maxim.

Timpul este O(n), memoria pentru date O(n), iar starea algoritmului O(1). Dacă nu ai nevoie de vector ulterior, poți procesa valorile direct la citire și reduce memoria totală la O(1). Sortarea ar rezolva problema în O(n log n), dar face mai mult decât este necesar.

Exersează

Testează 8, apoi 8 8, apoi 8 3 8. Primele două cazuri nu au două valori distincte; ultimul produce 8 3. Pentru -7 -2 -9 -2, răspunsul este -2 -7.

Modifică cerința pentru cele mai mici două valori distincte. Rescrie întâi comparațiile pe hârtie; nu schimba mecanic doar numele variabilelor. Ca extensie, justifică de ce un indicator separat este mai sigur decât o valoare santinelă aleasă din domeniul intrării.

Revezi inițializarea maximelor și minimelor, indicii vectorului și alternativa bazată pe sortare.

Întrebări frecvente

Ce înseamnă două maxime distincte într-un vector?

Sunt cele mai mari două valori diferite, nu două poziții diferite. Pentru 7 7 3 5, răspunsul este 7 și 5; cele două apariții ale lui 7 reprezintă aceeași valoare.

Trebuie să sortez vectorul pentru al doilea maxim distinct?

Nu. Poți păstra maximul, al doilea maxim și un indicator al existenței acestuia într-o singură parcurgere. Timpul este O(n), iar starea suplimentară a calculului este O(1).

Ce rezultat are un vector cu toate elementele egale?

Nu există două maxime distincte. Lecția afișează NU EXISTA. Un indicator separat evită confundarea absenței celui de-al doilea maxim cu o valoare validă, cum ar fi zero sau un număr negativ.