ການໃຫ້ແຖວຂອງເຄື່ອງຄົ້ນຫາທຸກໆຄູ່ Symmetric Symptoms ໃນນັ້ນ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon Capgemini Cisco ບໍ່ເສຍຄ່າ ຫ້ອງທົດລອງ Moonfrog Opera Xome
Array Hash

ຊອກຫາຄູ່ຊີເມັນທັງ ໝົດ - ທ່ານແມ່ນຄູ່ ໜຶ່ງ ຂອງ array. ທ່ານຕ້ອງຊອກຫາຄູ່ຊີເມັນໃນມັນ. ຄູ່ຄູ່ສະຫຼຽງຖືກກ່າວເຖິງວ່າມີຄວາມສົມດຸນເມື່ອຄູ່ເວົ້າ (a, b) ແລະ (c, d) ໃນນັ້ນ 'b' ເທົ່າກັບ 'c' ແລະ 'a' ແມ່ນເທົ່າກັບ 'd', ນັ້ນແມ່ນ, (1 , 2) ແມ່ນຄູ່ຄູ່ຂອງ (2, 1).

ຍົກຕົວຢ່າງ

ການໃຫ້ແຖວຂອງເຄື່ອງຄົ້ນຫາທຸກໆຄູ່ Symmetric Symptoms ໃນນັ້ນ

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

ສູດການຄິດໄລ່ເພື່ອຊອກຫາຄູ່ຄູ່ທີ່ມີຄວາມສອດຄ່ອງ

  1. ປະກາດກ HashMap.
  2. ໃນຂະນະທີ່ i <n (ຄວາມຍາວຂອງອາເລ)
    1. ທີ່ກໍານົດໄວ້ firstValue ເພື່ອຈັດຮຽງ [i] [0] ແລະ secondValue to arr [i] [1].
    2. ກວດເບິ່ງວ່າມູນຄ່າຂອງ SecondValue ບໍ່ແມ່ນ null ແລະຖ້າວ່າມູນຄ່າຂອງ SecondValue ແມ່ນເທົ່າກັບ firstValue
    3. ຖ້າຖືກຕ້ອງ, ຈາກນັ້ນພິມຄັ້ງທີສອງແລະ ທຳ ອິດ.
    4. ຄົນອື່ນໃສ່ the firstValue ແລະ secondValue ໃສ່ Hashmap.
  3. ເຮັດເລື້ມຄືນຂະບວນການຈາກ a ເຖິງ d ຈົນເຖິງ loop.

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ມອບຄູ່ຄູ່, ພາຍໃນນັ້ນມີບາງຄູ່ສົມມາດຖານທີ່ມີຢູ່. ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາກ່າວວ່າພວກເຮົາຕ້ອງຊອກຫາຄູ່ຄູ່ທີ່ມີຮູບແບບສົມມາດທີ່ມີໃນແຖວ. ພວກເຮົາພຽງແຕ່ສາມາດໃຊ້ສອງ loops ແລະຂວາງທັງສອງຂອດ ໜຶ່ງ ເທື່ອລະອັນ. ແຕ່ມັນເຮັດໃຫ້ພວກເຮົາມີເວລາສັບສົນຫຼາຍແລະພວກເຮົາບໍ່ສາມາດມີລະຫັດທີ່ມີປະສິດຕິພາບ. ພວກເຮົາພະຍາຍາມໃຊ້ວິທີການທີ່ດີກວ່າເພື່ອຈັດຮຽງພວກມັນເປັນ ລຳ ດັບໂດຍສະເພາະແຕ່ມັນກໍ່ຕ້ອງໃຊ້ປະສິດທິພາບຂອງພວກເຮົາ. ສະນັ້ນເພື່ອໃຫ້ໄດ້ໂປແກຼມທີ່ມີປະສິດຕິພາບພວກເຮົາຕ້ອງໄດ້ໃຊ້ hashing.

ໂດຍການໃຊ້ hashmap, ພວກເຮົາເກັບຮັກສາອົງປະກອບ ທຳ ອິດຂອງຄູ່ໃຫ້ firstValue ແລະອົງປະກອບທີສອງຂອງ secondValue, ພວກເຮົາສາມາດ ນຳ ໃຊ້ທັງສອງສ່ວນປະກອບຂອງຄູ່ເປັນກຸນແຈແລະຄຸນຄ່າ. ພວກເຮົາຈະຄົ້ນຫາມັນຢູ່ໃນແຜນທີ່ໂດຍການປຽບທຽບກຸນແຈຂອງຄູ່ ໜຶ່ງ ກັບມູນຄ່າຂອງອີກຄູ່ ໜຶ່ງ ແລະຄ່າຂອງຄູ່ດຽວກັນກັບກຸນແຈຂອງກຸນແຈຂອງຄູ່ອື່ນ.

ພວກເຮົາ ກຳ ລັງໃຊ້ hashmap ໃຫ້ພວກເຮົາພິຈາລະນາຕົວຢ່າງ ສຳ ລັບຄູ່, ຊອກຄູ່ສົມມາດໃນມັນ

ຍົກຕົວຢ່າງ

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

ພວກເຮົາຈະເກັບຮັກສາມູນຄ່າຂອງຄູ່ຂອງ array ເຂົ້າໃນ firstValue ແລະ secondValue ແລະຫຼັງຈາກນັ້ນພວກເຮົາຈະກວດສອບມັນ.

i = 0,

firstValue = ມາຮອດ [i] [0] // ຄູ່ອົງປະກອບທີ 1

secondValue = ມາຮອດ [i] [1] // ຄູ່ອົງປະກອບທີ 2

firstValue = 1, secondValue = 2

ພວກເຮົາຈະກວດເບິ່ງ 1 ຖ້າມັນມີຄ່າຢູ່ໃນແຜນທີ່ແລະເງື່ອນໄຂທີ່ບໍ່ຖືກຕ້ອງດັ່ງນັ້ນມັນຈະເອົາທັງສອງມູນຄ່າເຂົ້າໃນແຜນທີ່.

ແຜນທີ່ = [{1: 2}]

i = 1,

firstValue = ມາຮອດ [i] [0] // ຄູ່ອົງປະກອບທີ 1

secondValue = ມາຮອດ [i] [1] // ຄູ່ອົງປະກອບທີ 2

firstValue = 30, secondValue = 40

ພວກເຮົາຈະກວດເບິ່ງ 30 ຖ້າມັນມີຄ່າຢູ່ໃນແຜນທີ່ແລະເງື່ອນໄຂທີ່ບໍ່ຖືກຕ້ອງດັ່ງນັ້ນມັນຈະເອົາທັງສອງມູນຄ່າເຂົ້າໃນແຜນທີ່.

ແຜນທີ່ = [{1: 2}, {30:40}]

i = 2,

firstValue = ມາຮອດ [i] [0] // ຄູ່ອົງປະກອບທີ 1

secondValue = ມາຮອດ [i] [1] // ຄູ່ອົງປະກອບທີ 2

firstValue = 6, secondValue = 9

ພວກເຮົາຈະກວດເບິ່ງ 6 ຖ້າມັນມີຄ່າຢູ່ໃນແຜນທີ່ແລະເງື່ອນໄຂທີ່ບໍ່ຖືກຕ້ອງດັ່ງນັ້ນມັນຈະເອົາທັງສອງມູນຄ່າເຂົ້າໃນແຜນທີ່.

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

i = 3,

firstValue = ມາຮອດ [i] [0] // ຄູ່ອົງປະກອບທີ 1

secondValue = ມາຮອດ [i] [1] // ຄູ່ອົງປະກອບທີ 2

firstValue = 2, secondValue = 1

ພວກເຮົາຈະກວດເບິ່ງ 1 ຖ້າວ່າມັນມີຄຸນຄ່າຢູ່ໃນແຜນທີ່ແລະມັນມີຢູ່ເປັນ '2', ແລ້ວພວກເຮົາຈະກວດສອບ, ຖ້າວ່າສ່ວນປະກອບຂອງ SecondValue ເທົ່າກັບ firstValue ແລະເງື່ອນໄຂນີ້ກໍ່ຍັງພໍໃຈ.

ດັ່ງນັ້ນພວກເຮົາຈຶ່ງພິມ (1, 2)

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

i = 4,

firstValue = ມາຮອດ [i] [0] // ຄູ່ອົງປະກອບທີ 1

secondValue = ມາຮອດ [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 Program ເພື່ອຊອກຫາຄູ່ທັງ ໝົດ ຂອງ symmetric

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" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ນັບຕັ້ງແຕ່ພວກເຮົາໄດ້ເກັບຮັກສາອົງປະກອບຕ່າງໆໄວ້ໃນແຜນທີ່. ຄວາມສັບສົນຂອງພື້ນທີ່ແມ່ນເປັນເສັ້ນ.

ເອກະສານ