Хосуудын массив өгөгдсөн Түүнд бүх тэгш хэмтэй хосыг олоорой  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Capgemini Cisco Үнэгүй цэнэглэх Moonfrog лабораторууд Opera Xome
Array Хаш

Бүх тэгш хэмтэй хосыг олоорой массив. Та түүний тэгш хэмтэй хосыг олж мэдэх ёстой. Тэгш хэмтэй хосыг (a, b) ба (c, d) хосоор нь "b" нь "c", "a" нь "d" -тэй тэнцүү гэж хэлбэл тэгш хэмтэй гэж нэрлэдэг. , 1) нь (2, 2) -ийн тэгш хэмтэй хос юм.

Жишээ нь  

Хосуудын массив өгөгдсөн Түүнд бүх тэгш хэмтэй хосыг олооройPin

{{11, 20},{30,40},{4,5},{5,4},{40,30}}
(4, 5) (30, 40)

Бүх тэгш хэмтэй хосыг олох алгоритм  

  1. Мэдүүлэх a HashMap.
  2. Хэдийгээр би <n (массивын урт)
    1. нь чансаанд эхний үнэ цэнэ массив руу [i] [0] ба хоёр дахь утга arr [i] [1].
    2. SecondValue-ийн утга тэг биш байгаа эсэхийг, secondValue-ийн утга нь firstValue-тэй тэнцүү байгаа эсэхийг шалгана уу.
    3. Хэрэв үнэн бол secondValue ба firstValue-г хэвлэ.
    4. Else нь эхний үнэ цэнэ, хоёр дахь үнэ цэнийг Hashmap-д оруулсан.
  3. Үйлдлийг a-аас d-ээс давталт хүртэл давт.

Тайлбар

Бид массивын хосыг өгсөн, массив дотор тэгш хэмтэй хосууд байдаг. Асуудлын тайлбарт бид массивт байгаа бүх тэгш хэмтэй хосыг олох ёстой гэж хэлсэн. Бид зүгээр л хоёр гогцоо ашиглаж, массивыг хоёуланг нь нэг нэгээр нь туулж болно. Гэхдээ энэ нь бидэнд илүү их цаг хугацаа шаардагдах тул бид үр дүнтэй кодтой байж чадахгүй. Дараа нь тэдгээрийг тодорхой дарааллаар нь эрэмбэлэхийн тулд илүү сайн аргыг ашиглахыг хичээдэг боловч энэ нь бидний үр ашгийг шаарддаг. Тиймээс үр дүнтэй програмыг авахын тулд бид хэш хийх хэрэгтэй.

мөн үзнэ үү
Хамгийн урт Фибоначчийн дараагийн үр дагавар

Хэшмап ашиглан хослолын эхний элементийг эхлээд хадгална эхний үнэ цэнэ ба хоёр дахь элемент хоёр дахь утга, бид хос элементийн аль алиныг нь түлхүүр ба утга болгон ашиглаж болно. Бид үүнийг нэг хосын түлхүүрийг нөгөө хосын утгатай харьцуулж, ижил хосын утгыг нөгөө хосын түлхүүртэй харьцуулж газрын зураг дээрээс хайж олох болно.

Бид hashmap-ийг ашиглах гэж байгаа бөгөөд хос массивын жишээг авч үзье.

Жишээ нь

arr={{1, 2},{30,40},{6,9},{2,1},{9,6}}

Бид массивын хос утгыг firstValue, secondValue болгон хадгалж дараа нь шалгаж байх болно.

i = 0,

firstValue = arr [i] [0] // хос 1-р элемент

secondValue = arr [i] [1] // хос 2-р элемент

firstValue = 1, secondValue = 2

Газрын зураг дээр утга байгаа бол худал гэсэн нөхцөлтэй байгаа тул бид 1-ийг шалгаж, хоёулаа газрын зураг руу оруулна.

Газрын зураг = [{1: 2}]

i = 1,

firstValue = arr [i] [0] // хос 1-р элемент

secondValue = arr [i] [1] // хос 2-р элемент

firstValue = 30, secondValue = 40

Газрын зураг дээр утга байгаа бол худал гэсэн нөхцөлтэй байгаа тул бид 30-ийг шалгаж, хоёулаа газрын зураг руу оруулна.

Газрын зураг = [{1: 2}, {30:40}]

i = 2,

firstValue = arr [i] [0] // хос 1-р элемент

secondValue = arr [i] [1] // хос 2-р элемент

firstValue = 6, secondValue = 9

Газрын зураг дээр утга байгаа бол худал гэсэн нөхцөлтэй байгаа тул бид 6-ийг шалгаж, хоёулаа газрын зураг руу оруулна.

Map=[{1:2},{30:40},{6:9}]

i = 3,

firstValue = arr [i] [0] // хос 1-р элемент

secondValue = arr [i] [1] // хос 2-р элемент

firstValue = 2, secondValue = 1

Хэрэв газрын зураг дээр утга байгаа бөгөөд '1' гэж байгаа бол бид 2-ийг шалгаж, secondValue-ийн элемент нь firstValue-тэй тэнцүү байгаа бөгөөд энэ нөхцөл нь мөн хангагдах эсэхийг шалгана.

мөн үзнэ үү
Эхлээд эерэг алга байна

Тиймээс бид хэвлэнэ (1, 2)

Map=[{1:2},{30:40},{6:9}]

i = 4,

firstValue = arr [i] [0] // хос 1-р элемент

secondValue = arr [i] [1] // хос 2-р элемент

firstValue = 9, secondValue = 6

Хэрэв газрын зураг дээр утга байгаа бөгөөд энэ нь '6' гэж байгаа бол бид 9-г шалгаж, secondValue-ийн элемент нь firstValue-тэй тэнцүү байгаа эсэхийг шалгаж, энэ нөхцөл хангагдана.

Тиймээс бид (1, 2), (6, 9) хэвлэнэ.

Map=[{1:2},{30:40},{6:9}]

код  

Бүх тэгш хэмтэй хосыг олох програм C ++

#include<unordered_map>
#include<iostream>
using namespace std;
void getSymmetricPair(int arr[][2], int row)
{
    unordered_map<int, int> myMap;

    for (int i = 0; i < row; i++)
    {
        int firstValue = arr[i][0];
        int secondValue = arr[i][1];

        if (myMap.find(secondValue) != myMap.end() && myMap[secondValue] == firstValue)
        {
            cout << "(" << secondValue << ", " << firstValue << ")"<<" ";
        }
        else
        {
            myMap[firstValue] = secondValue;
        }
    }
}
int main()
{
    int arr[5][2]= {{11,20},{30,40},{4,5},{5,4},{40,30}};
    getSymmetricPair(arr, 5);
}
(4, 5) (30, 40)

Бүх тэгш хэмтэй хосыг олох Java програм

import java.util.HashMap;
class pairSymmetrics
{
    static void getSymmetricPair(int arr[][])
    {
        HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();

        for (int i = 0; i < arr.length; i++)
        {
            int firstValue = arr[i][0];
            int secondValue = arr[i][1];
            Integer val = hashmap.get(secondValue);

            if (val != null && val == firstValue)
            {
                System.out.print("(" + secondValue + ", " + firstValue + ")" + " ");
            }
            else
            {
                hashmap.put(firstValue, secondValue);
            }
        }
    }

    public static void main(String arg[])
    {
        int arr[][]= {{11,20},{30,40},{4,5},{5,4},{40,30}};
        getSymmetricPair(arr);

    }
}
(4, 5) (30, 40)

Нарийн төвөгтэй байдлын шинжилгээ  

Цаг хугацааны нарийн төвөгтэй байдал

O (N) хаана "N" массив дахь элементүүдийн тоо юм. Бид HashMap ашиглаж байсан тул оруулах / устгах / хайлт хийх боломжтой O (1) цаг хугацаа.

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" нь массив дахь элементүүдийн тоо юм. Бид газрын зураг дээр элементүүдийг хадгалсан тул. Сансрын нарийн төвөгтэй байдал нь шугаман хэлбэртэй байдаг.

Ашигласан материал