C++で指定されたN個の三角形の中から一意の三角形の数を見つけます

この問題では、サイズNの3つの配列s1 []、s2 []、およびs3 []が与えられ、N個の三角形を示します。私たちのタスクは、与えられたN個の三角形の中から一意の三角形の数を見つけることです。

三角形が一意であるためには、そのすべての辺が一意である必要があります。つまり、他の三角形が同じ辺を持つべきではありません。

問題を理解するために例を見てみましょう

入力

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

出力

1

説明

辺が124の三角形はユニークです。

ソリューションアプローチ

この問題の簡単な解決策は、一意の三角形の数を数えることです。

このために、最初に各三角形の辺を並べ替えてから、マップに保存します。値が一意である場合は、カウントを増やします。

ソリューションの動作を説明するプログラム

例

#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]] = m[triSides[i]] + 1;
   }
   map<vector<int>, int>::iterator itr;
   int uniqueTriCount = 0;
   for (itr = m.begin(); itr != m.end(); itr++) {
      if (itr->second == 1)
         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);
   cout<<"The number of unique triangles is "<<countUniqueTriangle(s1, s2, s3, N);
   return 0;
}

出力

The number of unique triangles is 1