distinct-numbers

Distinct Numbers

CSES easy

يُعطى لك قائمة من \(n\) أعداد صحيحة. أوجد عدد القيم المختلفة في القائمة.

القيود:

\(1 \le n \le 2 \cdot 10^5\)
\(1 \le x_i \le 10^9\)

الإدخال:

السطر الأول: عدد صحيح \(n\) — عدد القيم.
السطر الثاني: \(n\) عددًا \(x_1, x_2, \dots, x_n\).

المخرجات:

عدد صحيح واحد — عدد القيم المختلفة.

مثال:

الإدخال:

5
2 3 2 2 3

المخرجات:

الحل باستخدام المجموعة (set)

تخزّن المجموعة set كل قيمة مرة واحدة فقط: إدخال قيمة موجودة في المجموعة لا يغيّر شيئًا. ندخل كل القيم الـ \(n\) في مجموعة، وحجم المجموعة هو الجواب.

كل عملية إدخال تستغرق \(O(\log n)\)، لذا يعمل الحل كله في زمن \(O(n \log n)\).

#include <iostream>
#include <set>
using namespace std;

int main() {
    int n;
    cin >> n;

    set<int> values;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        values.insert(x);  // a repeated value is not inserted again
    }

    cout << values.size() << "\n";
}

الحل باستخدام الترتيب

بعد الترتيب تصبح القيم المتساوية متجاورة. لذلك تظهر القيمة \(x_i\) لأول مرة تمامًا عندما يكون \(i = 0\) أو \(x_i \ne x_{i-1}\). نعدّ هذه المواقع.

يستغرق الترتيب \(O(n \log n)\) وتستغرق الحلقة \(O(n)\)، لذا يعمل الحل كله في زمن \(O(n \log n)\). لا يحتاج هذا الحل إلى أي حاوية غير المصفوفة نفسها.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> x(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }

    sort(x.begin(), x.end());

    int distinct = 1;  // x[0] is always a new value
    for (int i = 1; i < n; i++) {
        if (x[i] != x[i - 1]) {
            distinct++;
        }
    }

    cout << distinct << "\n";
}