นับจำนวนองค์ประกอบที่แตกต่างกันในอาร์เรย์ใน C++

เราได้รับอาร์เรย์ที่ไม่ได้เรียงลำดับและมีค่าซ้ำกัน งานคือการนับจำนวนองค์ประกอบที่แตกต่างกัน (distinct elements)

ตัวอย่าง

Input − int arr[] = {1, 1, 2, 3, 3, 4, 4} Output − count is 4

คำอธิบาย − ค่าที่แตกต่างกันคือ 1,2,3,4 รวม 4 ค่า

Input − int arr[] = {1, 2, 3, 4, 5, 5, 5, 5} Output − count is 5

คำอธิบาย − ค่าที่แตกต่างกันคือ 1,2,3,4,5 รวม 5 ค่า

แนวทางการแก้ปัญหา

วิธีที่ 1: ใช้การเรียงลำดับ (Sorting)

• เรียงลำดับอาร์เรย์
• วนลูปข้ามค่าซ้ำกันและนับค่าที่แตกต่างกัน
• Complexity: O(n log n)

วิธีที่ 2: ไม่ใช้การเรียงลำดับ (Without Sorting)

• ใช้ลูปซ้อนตรวจสอบว่าค่านี้เคยเจอก่อนหน้านี้หรือไม่
• Complexity: O(n²)

ตัวอย่างโค้ด C++ (มีการเรียงลำดับ)

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

int distinctElements(int arr[], int n) {
    sort(arr, arr + n);
    int count = 0;
    for (int i = 0; i < n; i++) {
        while (i < n - 1 && arr[i] == arr[i + 1]) i++;
        count++;
    }
    return count;
}

int main() {
    int arr[] = {3, 6, 5, 8, 2, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "count is " << distinctElements(arr, n);
    return 0;
}

ตัวอย่างโค้ด C++ (ไม่มีการเรียงลำดับ)

#include <iostream>
using namespace std;

int countDistinct(int a[], int size) {
    int count = 1;
    for (int i = 1; i < size; i++) {
        int j;
        for (j = 0; j < i; j++) {
            if (a[i] == a[j]) break;
        }
        if (i == j) count++;
    }
    return count;
}

int main() {
    int a[] = {3, 6, 5, 8, 2, 3, 4};
    int size = sizeof(a) / sizeof(a[0]);
    cout << "count is " << countDistinct(a, size);
    return 0;
}

ผลลัพธ์

count is 6