Рубрики

По заданному массиву пар найти все симметричные пары в нем

Две пары (a, b) и (c, d) называются симметричными, если c равно b и a равно d. Например, (10, 20) и (20, 10) симметричны. По заданному массиву пар найти все симметричные пары в нем.

Можно предположить, что первые элементы всех пар различны.

Пример:

Input: arr[] = {{11, 20}, {30, 40}, {5, 10}, {40, 30}, {10, 5}}
Output: Following pairs have symmetric pairs
        (30, 40)
        (5, 10)  

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

Простое решение, чтобы пройти через каждую пару, и проверять каждую другую пару для симметричного. Это решение требует O (n 2 ) времени.

Лучшее решение — использовать сортировку. Сортировать все пары по первому элементу. Для каждой пары выполните бинарный поиск второго элемента в данном массиве, т. Е. Проверьте, существует ли второй элемент этой пары в качестве первого элемента в массиве. Если найдено, то сравните первый элемент пары со вторым элементом. Сложность времени этого решения O (nLogn).

Эффективным решением является использование хеширования. Первый элемент пары используется в качестве ключа, а второй элемент используется в качестве значения. Идея состоит в том, чтобы пройти все пары одну за другой. Для каждой пары проверьте, находится ли ее второй элемент в хеш-таблице. Если да, то сравните первый элемент со значением совпадающей записи хеш-таблицы. Если значение и первый элемент совпадают, то мы нашли симметричные пары. Иначе, вставьте первый элемент в качестве ключа и второй элемент в качестве значения.

Ниже приводится реализация этой идеи.

C / C ++

#include<bits/stdc++.h>

using namespace std;

  
// Программа на C ++ для поиска всех симметричных пар в заданном массиве пар
// Распечатать все пары, которые имеют симметричный аналог

void findSymPairs(int arr[][2], int row)

{

    // Создает пустой hashMap hM

    unordered_map<int, int> hM;

  

    // Пройти через данный массив

    for (int i = 0; i < row; i++)

    {

        // Первый и второй элементы текущей пары

        int first = arr[i][0];

        int sec   = arr[i][1];

  

        // Если найдено и значение в хэше совпадает с первым

        // элемент этой пары мы нашли симметрию

        if (hM.find(sec) != hM.end() && hM[sec] == first)

            cout << "(" << sec << ", " << first << ")" <<endl;

  

        else  // Остальное помещаем элемент sec этой пары в хеш

            hM[first] = sec;

    }

}

  
// Метод драйвера

int main()

{

    int arr[5][2];

    arr[0][0] = 11; arr[0][1] = 20;

    arr[1][0] = 30; arr[1][1] = 40;

    arr[2][0] = 5;  arr[2][1] = 10;

    arr[3][0] = 40;  arr[3][1] = 30;

    arr[4][0] = 10;  arr[4][1] = 5;

    findSymPairs(arr, 5);

}

  
// Это сделано Чхави

Джава

// Java-программа для поиска всех симметричных пар в заданном массиве пар

import java.util.HashMap;

   

class SymmetricPairs {

   

    // Распечатать все пары, которые имеют симметричный аналог

    static void findSymPairs(int arr[][])

    {

        // Создает пустой hashMap hM

        HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();

   

        // Пройти через данный массив

        for (int i = 0; i < arr.length; i++)

        {

            // Первый и второй элементы текущей пары

            int first = arr[i][0];

            int sec   = arr[i][1];

              

            // Ищите второй элемент этой пары в хэше

            Integer val = hM.get(sec);

   

            // Если найдено и значение в хэше совпадает с первым

            // элемент этой пары мы нашли симметрию

            if (val != null && val == first)

               System.out.println("(" + sec + ", " + first + ")");

                 

            else  // Остальное помещаем элемент sec этой пары в хеш

               hM.put(first, sec);

        }

    }

   

    // Метод драйвера

    public static void main(String arg[])

    {

        int arr[][] = new int[5][2];

        arr[0][0] = 11; arr[0][1] = 20;

        arr[1][0] = 30; arr[1][1] = 40;

        arr[2][0] = 5;  arr[2][1] = 10;

        arr[3][0] = 40;  arr[3][1] = 30;

        arr[4][0] = 10;  arr[4][1] = 5;

        findSymPairs(arr);

    }

}

python3

# Программа Python3, чтобы найти все симметричные
# пар в данном массиве пар.

  
# Распечатать все пары, которые имеют
# симметричный аналог

def findSymPairs(arr, row):

  

    # Создает пустой hashMap hM

    hM = dict()

  

    # Пройти через данный массив

    for i in range(row):

          

        # Первый и второй элементы

        # текущей пары

        first = arr[i][0]

        sec = arr[i][1]

  

        # Если найдено и значение в хэше совпадает с первым

        # элемент этой пары мы нашли симметрию

        if (sec in hM.keys() and hM[sec] == first):

            print("(", sec,",", first, ")")

  

        else: # Остальное поставить сек элемент

              # эта пара в хэше

            hM[first] = sec

  
Код водителя

if __name__ == '__main__':

    arr = [[0 for i in range(2)] 

              for i in range(5)]

    arr[0][0], arr[0][1] = 11, 20

    arr[1][0], arr[1][1] = 30, 40

    arr[2][0], arr[2][1] = 5, 10

    arr[3][0], arr[3][1] = 40, 30

    arr[4][0], arr[4][1] = 10, 5

    findSymPairs(arr, 5)

  
# Этот код предоставлен Мохитом Кумаром

C #

// C # программа для поиска всех симметричных
// пары в заданном массиве пар

using System;

using System.Collections.Generic;

  

public class SymmetricPairs 

{

  

    // Распечатать все пары, которые имеют симметричный аналог

    static void findSymPairs(int [,]arr)

    {

        // Создает пустой hashMap hM

        Dictionary<int,int> hM = new Dictionary<int,int>();

        int val = 0;

          

        // Пройти через данный массив

        for (int i = 0; i < arr.GetLength(0); i++)

        {

            // Первый и второй элементы текущей пары

            int first = arr[i, 0];

            int sec = arr[i, 1];

              

            // Ищите второй элемент этой пары в хэше

            if(hM.ContainsKey(sec))

            val = hM[sec];

              

  

            // Если найдено и значение в хэше совпадает с первым

            // элемент этой пары мы нашли симметрию

            if (val != 0 && val == first)

            Console.WriteLine("(" + sec + ", " + first + ")");

                  

            else // Остальное помещаем элемент sec этой пары в хеш

            hM.Add(first, sec);

        }

    }

  

    // Код драйвера

    public static void Main(String []arg)

    {

        int [,]arr = new int[5, 2];

        arr[0, 0] = 11; arr[0, 1] = 20;

        arr[1, 0] = 30; arr[1, 1] = 40;

        arr[2, 0] = 5; arr[2, 1] = 10;

        arr[3, 0] = 40; arr[3, 1] = 30;

        arr[4, 0] = 10; arr[4, 1] = 5;

        findSymPairs(arr);

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

Following pairs have symmetric pairs
(30, 40)
(5, 10)

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

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

Рекомендуемые посты:

По заданному массиву пар найти все симметричные пары в нем

0.00 (0%) 0 votes