In Tất Cả Phần Tử Riêng Biệt Của Mảng Số Nguyên Trong C++

Trong bài toán này, chúng ta được cho một mảng các giá trị nguyên. Nhiệm vụ là in tất cả các phần tử riêng biệt của mảng. Đầu ra chỉ chứa các giá trị duy nhất.

Ví dụ để hiểu vấn đề:

Đầu vào: mảng = {1, 5, 7, 12, 1, 6, 10, 7, 5} → Đầu ra: 1 5 7 12 6 10

Để giải quyết, ta kiểm tra các phần tử mảng về tính duy nhất. Sử dụng hai vòng lặp lồng: vòng ngoài lấy giá trị, vòng trong kiểm tra phần còn lại. Nếu có nhiều giá trị giống nhau chỉ in một.

Ví Dụ 1: Sử Dụng Hai Vòng Lặp Lồng

Mã minh họa:

#include <iostream>
using namespace std;

void printDistinctValues(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        int j;
        for (j = 0; j < i; j++)
            if (arr[i] == arr[j])
                break;
        if (i == j)
            cout << arr[i] << "\t";
    }
}

int main() {
    int arr[] = {1, 5, 7, 12, 1, 6, 10, 7, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Các giá trị riêng biệt của mảng là:\n";
    printDistinctValues(arr, n);
    return 0;
}

Đầu Ra

Các phần tử riêng biệt của mảng là: 1 5 6 7 10 12

Giải pháp này dễ hiểu nhưng dùng hai vòng lặp làm độ phức tạp O(n²).

Ví Dụ 2: Sử Dụng Sắp Xếp

Trong mảng đã sắp xếp, các số giống nhau nằm liên tiếp. In phần tử riêng biệt dễ dàng hơn và tiết kiệm không gian.

#include <bits/stdc++.h>
using namespace std;

void printDistinctElements(int arr[], int n) {
    sort(arr, arr + n);
    for (int i = 0; i < n; i++) {
        while (i < n - 1 && arr[i] == arr[i + 1])
            i++;
        cout << arr[i] << "\t";
    }
}

int main() {
    int arr[] = {1, 5, 7, 12, 1, 6, 10, 7, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Các phần tử riêng biệt của mảng là:\n";
    printDistinctElements(arr, n);
    return 0;
}

Đầu Ra

Các phần tử riêng biệt của mảng là: 1 5 6 7 10 12

Ví Dụ 3: Sử Dụng Tập Hợp (Hash Set) Theo Dõi Phần Tử Đã Thấy

Duyệt mảng, theo dõi các phần tử đã gặp bằng unordered_set.

#include<bits/stdc++.h>
using namespace std;

void printDistinctElements(int arr[], int n) {
    unordered_set<int> visited;
    for (int i = 0; i < n; i++) {
        if (visited.find(arr[i]) == visited.end()) {
            visited.insert(arr[i]);
            cout << arr[i] << "\t";
        }
    }
}

int main() {
    int arr[] = {1, 5, 7, 12, 1, 6, 10, 7, 5};
    int n = 7;
    cout << "Các số riêng biệt của mảng là:\n";
    printDistinctElements(arr, n);
    return 0;
}

Đầu Ra

Các số riêng biệt của mảng là: 1 5 7 12 6 10