ການນັບ ຈຳ ນວນຄູ່ຄູ່ດັດສະນີທີ່ມີສ່ວນປະກອບເທົ່າທຽມກັນໃນແຖວ  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon Atlassian Citadel ເຟສບຸກ Intuit Snapdeal Square Yandex
Array Hash ຊອກຫາ ຮຽງລໍາດັບ

ສົມມຸດວ່າ, ພວກເຮົາໄດ້ມອບ ໝາຍ integer array. ບັນຫາ“ ຈຳ ນວນຄູ່ຂອງດັດສະນີທີ່ມີສ່ວນປະກອບເທົ່າທຽມກັນໃນຂບວນການ” ຂໍໃຫ້ຊອກຮູ້ບໍ່ມີຄູ່ດັດສະນີ (i, ທ) ໃນແບບທີ່ arr [i] = ມາຮອດ [j] ແລະ i ບໍ່ເທົ່າກັບ j.

ຍົກຕົວຢ່າງ  

arr[] = {2,3,1,2,3,1,4}
3

ຄໍາອະທິບາຍ

ຄູ່ຂອງຕົວຊີ້ວັດແມ່ນ: (0, 3), (1, 4), (2, 5)

ການນັບ ຈຳ ນວນຄູ່ຄູ່ດັດສະນີທີ່ມີສ່ວນປະກອບເທົ່າທຽມກັນໃນແຖວPin

arr[] = {3, 3, 1, 4}
1

ຄໍາອະທິບາຍ

ຄູ່ຂອງຕົວຊີ້ວັດແມ່ນ: (0, 1)

ລະບົບວິເຄາະ  

  1. ປະກາດກ ແຜນທີ່.
  2. Traverse ໄດ້ array ແລະນັບແລະເກັບ ກຳ ຄວາມຖີ່ຂອງແຕ່ລະສ່ວນປະກອບເຂົ້າໃນແຜນທີ່.
  3. ຕັ້ງຄ່າຜົນຜະລິດໃຫ້ 0.
  4. ຂ້າມແຜນທີ່ແລະຮັບຄວາມຖີ່ຂອງແຕ່ລະອົງປະກອບຈາກແຜນທີ່.
  5. ເຮັດຜົນຜະລິດ + = (VAL * (VAL - 1)) / 2, VAL ແມ່ນຄວາມຖີ່ຂອງແຕ່ລະອົງປະກອບ.
  6. ກັບຄືນຜົນຜະລິດ.

ຄໍາອະທິບາຍ

ພວກເຮົາໄດ້ມອບ array ຂອງເລກເຕັມ, ພວກເຮົາໄດ້ຮ້ອງຂໍໃຫ້ຊອກຫາຂໍ້ມູນທັງ ໝົດ ບໍ່. ຄູ່ທີ່ມີຢູ່ໃນວົງຈອນດັ່ງກ່າວວ່າຕົວຊີ້ວັດຂອງພວກມັນບໍ່ຄືກັນແຕ່ວ່າອົງປະກອບທີ່ຢູ່ໃນຕົວຊີ້ບອກນັ້ນຄວນຄືກັນ. ດັ່ງນັ້ນພວກເຮົາຈະໃຊ້ a ແຮກ ສຳ ລັບມັນ. Hashing ແມ່ນວິທີການທີ່ດີກວ່າວິທີການບັງຄັບໃຊ້ທີ່ພວກເຮົາຕ້ອງໄປຢ້ຽມຢາມທຸກໆອົງປະກອບເຫຼົ່ານັ້ນໂດຍໃຊ້ເວລາພິເສດ ໂອ (ນ2). ດັ່ງນັ້ນພວກເຮົາຈຶ່ງຫລີກລ້ຽງສິ່ງນັ້ນ.

ພວກເຮົາຈະປະກາດແຜນທີ່, ເກັບເອົາແຕ່ລະອົງປະກອບ, ນັບແລະເກັບຄວາມຖີ່ຂອງແຕ່ລະອົງປະກອບເຂົ້າໃນແຜນທີ່, ຖ້າມັນມີຢູ່ໃນແຜນທີ່ແລ້ວ, ສ້າງສະຖານທີ່ໃຫ້, ຖ້າມັນ ນຳ ສະ ເໜີ ແລ້ວພຽງແຕ່ເພີ່ມຄວາມຖີ່ຂອງມັນໂດຍ 1

ເບິ່ງ
Swap Nodes ໃນ Pairs Leetcode Solutions

ເພື່ອໃຊ້ສູດປະສົມປະສານ, ພວກເຮົາຕ້ອງນັບຄວາມຖີ່ຂອງແຕ່ລະຕົວເລກ. ພວກເຮົາ ກຳ ລັງຈະເລືອກຄູ່ຫຼາຍຄູ່ທີ່ພໍໃຈກັບສະພາບການຂອງອົງປະກອບທີ່ເທົ່າທຽມກັນແຕ່ບໍ່ແມ່ນຕົວຊີ້ບອກຂອງມັນ. ພວກເຮົາສາມາດສົມມຸດໄດ້ວ່າຕົວເລກໃດໆທີ່ມີຢູ່ໃນອາເລປະກົດວ່າ k ເວລາໃດກໍ່ຕາມດັດສະນີເຖິງ kth index. ຈາກນັ້ນເລືອກເອົາສອງຕົວຊີ້ບອກກi ແລະy ເຊິ່ງຈະຖືກນັບເປັນ 1 ຄູ່. ຄ້າຍຄືກັນ, ກy ແລະx ຍັງສາມາດເປັນຄູ່. ສະນັ້ນ, nC2 ແມ່ນສູດ ສຳ ລັບການຄົ້ນຫາ ຈຳ ນວນຄູ່ທີ່ມາຮອດ [i] = ມາຮອດ [j] ກໍ່ເທົ່າກັບ x.

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

ລະຫັດ C ++ ເພື່ອຊອກຫານັບ ຈຳ ນວນຄູ່ຄູ່ດັດສະນີທີ່ມີສ່ວນປະກອບເທົ່າທຽມກັນໃນແຖວ  

#include<iostream>
#include<unordered_map>

using namespace std;

int getNoOfPairs(int arr[], int n)
{
    unordered_map<int, int> MAP;

    for (int i = 0; i < n; i++)
        MAP[arr[i]]++;

    int output = 0;
    for (auto it=MAP.begin(); it!=MAP.end(); it++)
    {
        int VAL = it->second;
        output += (VAL * (VAL - 1))/2;
    }
    return output;
}
int main()
{
    int arr[] = {2,3,1,2,3,1,4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getNoOfPairs(arr, n) << endl;
    return 0;
}
3

ລະຫັດ Java ເພື່ອຊອກຫານັບຂອງຄູ່ຄູ່ດັດສະນີທີ່ມີສ່ວນປະກອບເທົ່າທຽມກັນໃນແຖວ  

import java.util.HashMap;
import java.util.Map;

class countIndexPair
{
    public static int getNoOfPairs(int arr[], int n)
    {
        HashMap<Integer,Integer> MAP = new HashMap<>();

        for(int i = 0; i < n; i++)
        {
            if(MAP.containsKey(arr[i]))
                MAP.put(arr[i],MAP.get(arr[i]) + 1);
            else
                MAP.put(arr[i], 1);
        }
        int output=0;
        for(Map.Entry<Integer,Integer> entry : MAP.entrySet())
        {
            int VAL = entry.getValue();
            output += (VAL * (VAL - 1)) / 2;
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[]= {2,3,1,2,3,1,4};
        System.out.println(getNoOfPairs(arr,arr.length));
    }
}
3

ການວິເຄາະຄວາມສັບສົນ  

ຄວາມສັບສົນເວລາ

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.

ເບິ່ງ
Traversal ທາງສ່ວນຫນ້າຂອງ Iterative

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.