使用STL |集合1（使用集合）计算唯一三角形的数量-yiteyi-C++库

我们得到了n个三角形，以及它们的三条边的长度，a，b，c。现在我们需要从这些n个给定三角形中计算出唯一三角形的数量。如果两个三角形至少有一条边不同，则它们彼此不同。

null

例子：

Input: arr[] = {{1, 2, 2},
                {4, 5, 6}, 
                {4, 5, 6}    
Output: 2

Input: arr[] = {{4, 5, 6}, {6, 5, 4},
                {1, 2, 2}, {8, 9, 12}
Output: 3

我们强烈建议您尽量减少浏览器，并先自己尝试。

因为我们需要找到“唯一”三角形的数量，所以我们可以使用设置或者无序的集合。本文讨论了基于集合的方法。

如何将三面作为一个元素存储在容器中？我们使用STL 一对将所有三面存储在一起作为

pair <int, pair<int, int> >

我们一个接一个地将所有三角形插入集合中。但这种方法的问题是，边为{4,5,6}的三角形与边为{5,4,6}的三角形不同，尽管它们指的是同一个三角形。

为了处理这种情况，我们按排序顺序（根据边的长度）存储边，这里排序不是问题，因为我们只有三条边，我们可以在固定时间内对它们进行排序。例如，{5,4,6}被插入到集合中作为{4,5,6}

注意：我们可以通过make_pair（a，b）或简单地使用{a，b}来创建pair。

下面是C++实现上述思想：

                     // A C++ program to find number of unique Triangles                   
                     #include <bits/stdc++.h>                   
                     using                               namespace                               std;                   
                             
                     // Creating shortcut for an integer pair.                   
                     typedef                               pair<                               int                               ,                               int                               > iPair;                   
                             
                     // A structure to represent a Triangle with                   
                     // three sides as a, b, c                   
                     struct                               Triangle                   
                     {                   
                                         int                               a, b, c;                   
                     };                   
                             
                     // A function to sort three numbers a, b and c.                   
                     // This function makes 'a' smallest, 'b' middle                   
                     // and 'c' largest (Note that a, b and c are passed                   
                     // by reference)                   
                     int                               sort3(                               int                               &a,                               int                               &b,                               int                               &c)                   
                     {                   
                                         vector<                               int                               > arr({a, b, c});                   
                                         sort(arr.begin(), arr.end());                   
                                         a = arr[0]; b = arr[1]; c = arr[2];                   
                     }                   
                             
                     // Function returns the number of unique Triangles                   
                     int                               countUniqueTriangles(                               struct                               Triangle arr[],                   
                                         int                               n)                   
                     {                   
                                         // A set which consists of unique Triangles                   
                                         set < pair<                               int                               , iPair > > s;                   
                             
                                         // Insert all triangles one by one                   
                                         for                               (                               int                               i=0; i<n; i++)                   
                                         {                   
                                         // Find three sides and sort them                   
                                         int                               a = arr[i].a, b = arr[i].b, c = arr[i].c;                   
                                         sort3(a, b, c);                   
                             
                                         // Insert a triangle into the set                   
                                         s.insert({a, {b, c}});                   
                                         }                   
                             
                                         // Return set size                   
                                         return                               s.size();                   
                     }                   
                             
                     // Driver program to test above function                   
                     int                               main()                   
                     {                   
                                         // An array of structure to store sides of 6 Triangles                   
                                         struct                               Triangle arr[] = {{3, 2, 2}, {3, 4, 5}, {1, 2, 2},                   
                                         {2, 2, 3}, {5, 4, 3}, {6, 4, 5}};                   
                                         int                               n =                               sizeof                               (arr)/                               sizeof                               (Triangle);                   
                             
                                         cout <<                               "Number of Unique Triangles are "                   
                                         << countUniqueTriangles(arr, n);                   
                                         return                               0;                   
                     }                   

输出：

Number of Unique Triangles are 4

上述解决方案的时间复杂度为O（n logn），因为set需要O（logn）时间进行插入。

我们可以使用无序集 .但使用无序_集需要编写一个哈希函数，因为库中没有定义成对的哈希函数。