หาจำนวนสามเหลี่ยมที่ไม่ซ้ำกันจาก N สามเหลี่ยมด้วย C++

ภาพรวมปัญหา

ได้รับอาร์เรย์ 3 อาร์เรย์ s1[], s2[], s3[] ขนาด N แทนด้านของ N สามเหลี่ยม ต้องหาจำนวนสามเหลี่ยมที่ "ไม่ซ้ำกัน" (unique) หมายถึงไม่มีสามเหลี่ยมอื่นที่มีชุดด้านเหมือนกัน

ตัวอย่าง

อินพุต

s1[] = {1, 5, 3}
s2[] = {2, 3, 2}
s3[] = {4, 2, 5}

เอาต์พุต

1

คำอธิบาย

สามเหลี่ยมที่ 1: 1, 2, 4 (unique)
สามเหลี่ยมที่ 2: 5, 3, 2 → เรียง: 2, 3, 5
สามเหลี่ยมที่ 3: 3, 2, 5 → เรียง: 2, 3, 5 (ซ้ำกับสามเหลี่ยมที่ 2)

วิธีแก้ปัญหา

1. เรียงลำดับด้านของแต่ละสามเหลี่ยม
2. เก็บใน map นับความถี่
3. นับจำนวนที่มีความถี่ = 1

โค้ดตัวอย่าง

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

int countUniqueTriangle(int a[], int b[], int c[], int n) {
    vector<int> triSides[n];
    map<vector<int>, int> m;
    
    for (int i = 0; i < n; i++) {
        triSides[i].push_back(a[i]);
        triSides[i].push_back(b[i]);
        triSides[i].push_back(c[i]);
        sort(triSides[i].begin(), triSides[i].end());
        m[triSides[i]]++;
    }
    
    int uniqueTriCount = 0;
    for (auto itr = m.begin(); itr != m.end(); itr++) {
        if (itr->second == 1)
            uniqueTriCount++;
    }
    return uniqueTriCount;
}

int main() {
    int s1[] = { 1, 5, 3 };
    int s2[] = { 2, 3, 2 };
    int s3[] = { 4, 2, 5 };
    int N = sizeof(s1) / sizeof(s1[0]);
    cout << "The number of unique triangles is " << countUniqueTriangle(s1, s2, s3, N);
    return 0;
}

เอาต์พุต

The number of unique triangles is 1

สรุป

ใช้ map<vector<int>, int> เพื่อนับความถี่ของชุดด้านที่เรียงแล้ว Complexity: O(N log N)