ਐਰੇ ਵਿੱਚ ਬਰਾਬਰ ਤੱਤ ਵਾਲੇ ਇੰਡੈਕਸ ਜੋੜਿਆਂ ਦੀ ਗਿਣਤੀ  


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ Atlassian ਕਿਲੇ ਫੇਸਬੁੱਕ Intuit Snapdeal Square ਯੈਨਡੇਕਸ
ਅਰੇ ਹੈਸ਼ ਖੋਜ ਕਰਨਾ ਲੜੀਬੱਧ

ਮੰਨ ਲਓ, ਅਸੀਂ ਇਕ ਦਿੱਤਾ ਹੈ ਪੂਰਨ ਅੰਕ ਐਰੇ. ਸਮੱਸਿਆ "ਐਰੇ ਵਿਚ ਬਰਾਬਰ ਤੱਤ ਵਾਲੇ ਇੰਡੈਕਸ ਜੋੜਿਆਂ ਦੀ ਗਿਣਤੀ" ਸੂਚਕਾਂਕ ਦੀ ਜੋੜੀ ਦੀ ਗਿਣਤੀ ਲੱਭਣ ਲਈ ਕਹਿੰਦੀ ਹੈ (i, ਜੇ) ਇਸ ਤਰੀਕੇ ਨਾਲ ਐਰ [i] = ਅਰਰ [ਜੇ] ਅਤੇ i ਦੇ ਬਰਾਬਰ ਨਹੀਂ ਹੈ j.

ਉਦਾਹਰਨ  

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

ਕਥਾ

ਸੂਚਕਾਂਕ ਦੇ ਜੋੜੇ ਹਨ: (0, 3), (1, 4), (2, 5)

ਐਰੇ ਵਿੱਚ ਬਰਾਬਰ ਤੱਤ ਵਾਲੇ ਇੰਡੈਕਸ ਜੋੜਿਆਂ ਦੀ ਗਿਣਤੀਪਿੰਨ

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

ਕਥਾ

ਸੂਚਕਾਂਕ ਦੇ ਜੋੜੇ ਹਨ: (0, 1)

ਐਲਗੋਰਿਥਮ  

  1. ਘੋਸ਼ਣਾ ਏ ਨਕਸ਼ਾ.
  2. ਪਾਰ ਕਰੋ ਐਰੇ ਅਤੇ ਨਕਸ਼ੇ ਵਿੱਚ ਹਰੇਕ ਤੱਤ ਦੀ ਬਾਰੰਬਾਰਤਾ ਨੂੰ ਗਿਣੋ ਅਤੇ ਸਟੋਰ ਕਰੋ.
  3. 0 ਨੂੰ ਆਉਟਪੁੱਟ ਦਿਓ.
  4. ਨਕਸ਼ੇ ਨੂੰ ਪਾਰ ਕਰੋ ਅਤੇ ਨਕਸ਼ੇ ਤੋਂ ਹਰੇਕ ਤੱਤ ਦੀ ਬਾਰੰਬਾਰਤਾ ਪ੍ਰਾਪਤ ਕਰੋ.
  5. ਆਉਟਪੁੱਟ + = (VAL * (VAL - 1)) / 2, VAL ਹਰ ਇਕਾਈ ਦੀ ਬਾਰੰਬਾਰਤਾ ਹੈ.
  6. ਵਾਪਸੀ ਆਉਟਪੁੱਟ.

ਕਥਾ

ਅਸੀਂ ਇੱਕ ਦਿੱਤਾ ਹੈ ਐਰੇ ਪੂਰਨ ਅੰਕ ਦੇ, ਅਸੀਂ ਕੁਲ ਨੰਬਰ ਲੱਭਣ ਲਈ ਕਿਹਾ ਹੈ. ਐਰੇ ਵਿਚ ਮੌਜੂਦ ਜੋੜਿਆਂ ਦੇ ਜੋੜ ਜਿਵੇਂ ਕਿ ਉਨ੍ਹਾਂ ਦੇ ਸੂਚਕ ਇਕੋ ਜਿਹੇ ਨਹੀਂ ਹੁੰਦੇ ਬਲਕਿ ਉਨ੍ਹਾਂ ਸੂਚਕਾਂਕ ਦੇ ਤੱਤ ਇਕੋ ਜਿਹੇ ਹੋਣੇ ਚਾਹੀਦੇ ਹਨ. ਇਸ ਲਈ ਅਸੀਂ ਏ ਦੀ ਵਰਤੋਂ ਕਰਨ ਜਾ ਰਹੇ ਹਾਂ ਹੈਸ਼ਿੰਗ ਇਸ ਦੇ ਲਈ. ਜ਼ਹਾਜ਼ ਫੋਰਸ forceੰਗ ਨਾਲੋਂ ਹੈਸ਼ਿੰਗ ਇੱਕ ਵਧੀਆ ਤਰੀਕਾ ਹੈ ਜਿਸ ਵਿੱਚ ਸਾਨੂੰ ਵਾਧੂ ਸਮੇਂ ਦੀ ਵਰਤੋਂ ਕਰਦਿਆਂ ਉਹਨਾਂ ਸਾਰੇ ਤੱਤਾਂ ਨੂੰ ਵੇਖਣਾ ਪੈਂਦਾ ਹੈ ਓ (ਐਨ2). ਇਸ ਲਈ ਅਸੀਂ ਇਸ ਤੋਂ ਪਰਹੇਜ਼ ਕਰ ਰਹੇ ਹਾਂ.

ਅਸੀਂ ਇਕ ਨਕਸ਼ੇ ਦੀ ਘੋਸ਼ਣਾ ਕਰਾਂਗੇ, ਹਰ ਇਕ ਤੱਤ ਨੂੰ ਚੁੱਕਣਗੇ, ਹਰੇਕ ਤੱਤ ਦੀ ਬਾਰੰਬਾਰਤਾ ਨੂੰ ਨਕਸ਼ੇ ਵਿਚ ਗਿਣੋਗੇ ਅਤੇ ਸਟੋਰ ਕਰਾਂਗੇ, ਜੇ ਇਹ ਪਹਿਲਾਂ ਹੀ ਨਕਸ਼ੇ ਵਿਚ ਮੌਜੂਦ ਹੈ, ਤਾਂ ਇਸ ਲਈ ਜਗ੍ਹਾ ਬਣਾਓ, ਜੇ ਇਹ ਪਹਿਲਾਂ ਹੀ ਮੌਜੂਦ ਹੈ ਤਾਂ ਇਸ ਦੀ ਬਾਰੰਬਾਰਤਾ ਨੂੰ 1 ਨਾਲ ਵਧਾ ਦੇਵੇਗਾ.

ਇਹ ਵੀ ਵੇਖੋ
ਪੇਅਰਜ਼ ਲੈਟਕੋਡ ਸਲਿ .ਸ਼ਨਜ਼ ਵਿਚ ਨੋਡਾਂ ਨੂੰ ਸਵੈਪ ਕਰੋ

ਸੁਮੇਲ ਫਾਰਮੂਲਾ ਵਰਤਣ ਲਈ, ਸਾਨੂੰ ਹਰੇਕ ਨੰਬਰ ਦੀ ਬਾਰੰਬਾਰਤਾ ਨੂੰ ਗਿਣਨਾ ਪੈਂਦਾ ਹੈ. ਅਸੀਂ ਕਈ ਜੋੜਿਆਂ ਦੀ ਚੋਣ ਕਰਨ ਜਾ ਰਹੇ ਹਾਂ ਜੋ ਬਰਾਬਰ ਤੱਤਾਂ ਦੀ ਦਿੱਤੀ ਗਈ ਸ਼ਰਤ ਨੂੰ ਪੂਰਾ ਕਰਦੇ ਹਨ ਪਰ ਉਨ੍ਹਾਂ ਦੇ ਸੂਚਕਾਂਕ ਨਹੀਂ. ਅਸੀਂ ਇਹ ਮੰਨ ਸਕਦੇ ਹਾਂ ਕਿ ਕੋਈ ਵੀ ਅੰਕ ਜੋ ਐਰੇ ਵਿਚ ਮੌਜੂਦ ਹੈ, kth ਇੰਡੈਕਸ ਤਕ ਕਿਸੇ ਵੀ ਇੰਡੈਕਸ ਵਿਚ k ਵਾਰ ਦਿਖਾਈ ਦਿੰਦਾ ਹੈ. ਫਿਰ ਕੋਈ ਵੀ ਦੋ ਸੂਚਕਾਂਕ ਚੁਣੋi ਅਤੇ ਇੱਕy ਜੋ ਕਿ 1 ਜੋੜਾ ਗਿਣਿਆ ਜਾਵੇਗਾ. ਇਸੇ ਤਰ੍ਹਾਂ ਏy ਅਤੇ ਇੱਕx ਜੋੜਾ ਵੀ ਹੋ ਸਕਦਾ ਹੈ. ਇਸ ਲਈ, nC2 ਜੋੜਿਆਂ ਦੀ ਗਿਣਤੀ ਦਾ ਪਤਾ ਲਗਾਉਣ ਲਈ ਇਕ ਫਾਰਮੂਲਾ ਹੈ ਜਿਸ ਲਈ ਐਰ [i] = ਅਰਰ [ਜੇ] ਵੀ x ਦੇ ਬਰਾਬਰ ਹੈ.

ਐਰੇ ਨੂੰ ਟ੍ਰਾਂਸਵਲ ਕਰਨ ਤੋਂ ਬਾਅਦ, ਅਤੇ ਹਰੇਕ ਤੱਤ ਅਤੇ ਇਸ ਦੀ ਮੌਜੂਦਗੀ ਨੂੰ ਨਕਸ਼ੇ ਵਿਚ ਪਾਉਂਦੇ ਹੋਏ, ਅਸੀਂ ਨਕਸ਼ੇ ਨੂੰ ਪਾਰ ਕਰ ਦੇਵਾਂਗੇ, ਤੱਤ ਦੀ ਹਰੇਕ ਬਾਰੰਬਾਰਤਾ ਨੂੰ ਚੁਣਾਂਗੇ ਅਤੇ ਇਸ 'ਤੇ ਇਕ ਫਾਰਮੂਲਾ ਲਾਗੂ ਕਰਾਂਗੇ, ਆਉਟਪੁੱਟ ਦੇ ਨਾਲ ਜੋੜ ਕੇ ਇਸ ਨੂੰ ਆਉਟਪੁੱਟ ਵਿਚ ਸਟੋਰ ਕਰਾਂਗੇ. ਸਾਨੂੰ ਇਸ ਨੂੰ ਦੁਹਰਾਉਂਦੇ ਰਹਿਣਾ ਪੈਂਦਾ ਹੈ ਜਦ ਤਕ ਅਸੀਂ ਸਾਰੇ ਤੱਤਾਂ ਅਤੇ ਉਨ੍ਹਾਂ ਦੀਆਂ ਬਾਰੰਬਾਰਤਾ ਨੂੰ ਪਾਰ ਨਹੀਂ ਕਰਦੇ ਅਤੇ ਇਸ ਤੇ ਕੋਈ ਕਾਰਜ ਨਹੀਂ ਕਰਦੇ. ਅਤੇ ਅੰਤ ਵਿੱਚ, ਅਸੀਂ ਉਹ ਆਉਟਪੁੱਟ ਵਾਪਸ ਕਰਾਂਗੇ.

ਐਰੇ ਵਿਚ ਬਰਾਬਰ ਤੱਤ ਵਾਲੇ ਇੰਡੈਕਸ ਜੋੜਿਆਂ ਦੀ ਗਿਣਤੀ ਲੱਭਣ ਲਈ ਸੀ ++ ਕੋਡ  

#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

ਐਰੇ ਵਿੱਚ ਬਰਾਬਰ ਤੱਤ ਵਾਲੇ ਇੰਡੈਕਸ ਜੋੜਿਆਂ ਦੀ ਗਿਣਤੀ ਲੱਭਣ ਲਈ ਜਾਵਾ ਕੋਡ  

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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ  

ਟਾਈਮ ਜਟਿਲਤਾ

ਹੇ (n) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ.

ਇਹ ਵੀ ਵੇਖੋ
ਇਟਰੇਟਿਵ ਪੂਰਵ-ਆਰਡਰ ਟ੍ਰੈਵਰਸਾਲ

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਹੇ (n) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ.