Подсчитайте количество уникальных треугольников с помощью STL | Набор 1 (с использованием набора)

Опубликовано: 1 Января, 2022

Даны n треугольников, длина трех сторон которых a, b, c. Теперь нам нужно посчитать количество уникальных треугольников из этих n заданных треугольников. Два треугольника отличаются друг от друга, если у них есть хотя бы одна из сторон.

Пример:

 Ввод: arr [] = {{1, 2, 2},
                {4, 5, 6}, 
                {4, 5, 6} 
Выход: 2

Ввод: arr [] = {{4, 5, 6}, {6, 5, 4},
                {1, 2, 2}, {8, 9, 12}
Выход: 3

Мы настоятельно рекомендуем вам свернуть браузер и сначала попробовать это самостоятельно.

Поскольку нас просят найти количество «уникальных» треугольников, мы можем использовать либо set, либо unordered_set. В этом посте обсуждается подход, основанный на наборах.

Как сохранить три стороны как элемент в контейнере? Мы используем пару STL для хранения всех трех сторон вместе как

pair <int, pair<int, int> >

Поочередно вставляем в набор все треугольники. Но проблема с этим подходом состоит в том, что треугольник со сторонами как {4, 5, 6} отличается от треугольника со сторонами {5, 4, 6}, хотя они относятся к одному и тому же треугольнику.

Чтобы справиться с такими случаями, мы храним стороны в отсортированном порядке (на основе длины сторон), здесь сортировка не будет проблемой, поскольку у нас всего 3 стороны, и мы можем сортировать их за постоянное время. Например, {5, 4, 6} вставляется в набор как {4, 5, 6}

Примечание: мы можем создать пару либо с помощью make_pair (a, b), либо просто использовать {a, b}.

Ниже представлена реализация вышеизложенной идеи на 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;
 }

Выход:

 Количество уникальных треугольников - 4

Временная сложность вышеупомянутого решения составляет O (n Log n), поскольку установлено, что для вставки требуется время O (Log n).

Мы можем улучшить временную сложность до O (n), используя unordered_set. Но использование unordered_set требует написания хеш-функции, поскольку хеш-функция не определена в библиотеке для пар.

Связанная статья: Количество возможных треугольников

Эта статья предоставлена Чирагом Агравалом . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью и отправить ее по электронной почте на deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Хотите узнать о лучших видео и практических задачах, ознакомьтесь с базовым курсом C ++ для базового и продвинутого уровня C ++ и курсом C ++ STL для базового уровня плюс STL. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

C++ C

Подсчитайте количество уникальных треугольников с помощью STL | Набор 1 (с использованием набора)

РЕКОМЕНДУЕМЫЕ СТАТЬИ