Найдите количество уникальных треугольников среди заданных N треугольников

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

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

Примеры:

Input: a[] = {1, 2}, b[] = {2, 3}, c[] = {3, 5}
Output: 2
The triangles have sides 1, 2, 3 and 2, 3, 5 respectively.
None of them have same sides. Thus both are unique.
Input: a[] = {7, 5, 8, 2, 2}, b[] = {6, 7, 2, 3, 4}, c[] = {5, 6, 9, 4, 3}
Output: 1
Only triangle with sides 8, 2 and 9 is unique.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: Идея состоит в том, чтобы для каждого треугольника отсортировать все его стороны, а затем сохранить их на карте. Если все эти три стороны уже присутствуют на карте, увеличьте частоту на 1, иначе ее частота будет равна 1. Счетчик элементов карты, которые имеют частоту 1 в конце будут ответом.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to return the number of unique triangles
int UniqueTriangles(int a[], int b[], int c[], int n)
{
    vector<int> sides[n];
  
    // Map to store the frequency of triangles
    // with same sides
    map<vector<int>, int> m;
  
    for (int i = 0; i < n; i++) {
  
        // Push all the sides of the current triangle
        sides[i].push_back(a[i]);
        sides[i].push_back(b[i]);
        sides[i].push_back(c[i]);
  
        // Sort the three sides
        sort(sides[i].begin(), sides[i].end());
  
        // Store the frequency of the sides
        // of the triangle
        m[sides[i]] = m[sides[i]] + 1;
    }
  
    map<vector<int>, int>::iterator i;
  
    // To store the count of unique triangles
    int count = 0;
    for (i = m.begin(); i != m.end(); i++) {
  
        // If current triangle has unique sides
        if (i->second == 1)
            count++;
    }
  
    return count;
}
  
// Driver code
int main()
{
    int a[] = { 7, 5, 8, 2, 2 };
    int b[] = { 6, 7, 2, 3, 4 };
    int c[] = { 5, 6, 9, 4, 3 };
  
    int n = sizeof(a) / sizeof(int);
  
    cout << UniqueTriangles(a, b, c, n);
  
    return 0;
}

Python3

# Python3 implementation of the approach
from collections import defaultdict
  
# Function to return the number
# of unique triangles
def UniqueTriangles(a, b, c, n):
  
    sides = [None for i in range(n)]
  
    # Map to store the frequency of 
    # triangles with same sides
    m = defaultdict(lambda:0)
  
    for i in range(0, n):
  
        # Push all the sides of the current triangle
        sides[i] = (a[i], b[i], c[i]) 
  
        # Sort the three sides
        sides[i] = tuple(sorted(sides[i]))
  
        # Store the frequency of the sides
        # of the triangle
        m[sides[i]] += 1
  
    # To store the count of unique triangles
    count = 0
    for i in m: 
  
        # If current triangle has unique sides
        if m[i] == 1:
            count += 1
  
    return count
  
# Driver code
if __name__ == "__main__":
  
    a = [7, 5, 8, 2, 2] 
    b = [6, 7, 2, 3, 4] 
    c = [5, 6, 9, 4, 3] 
  
    n = len(a)
  
    print(UniqueTriangles(a, b, c, n))
      
# This code is contributed by Rituraj Jain

Output:

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

Найдите количество уникальных треугольников среди заданных N треугольников

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C++

Python3

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