अ‍ॅरेमध्ये समान घटकांसह निर्देशांक जोड्यांची संख्या


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन Atlassian किल्ला फेसबुक अंतर्ज्ञानाने जाणणे Snapdeal स्क्वेअर यांडेक्स
अरे हॅश शोधत आहे वर्गीकरण

समजा, आपण दिले आहे पूर्णांक अॅरे. “अ‍ॅरेमध्ये समान घटकांसह निर्देशांक जोड्यांची समस्या” ही समस्या निर्देशांकांच्या जोडीची संख्या शोधण्यासाठी विचारते (मी, जे) अशा प्रकारे अरे [i] = अरे [j] आणि 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. आउटपुट करा + = (व्हीएएल * (व्हीएएल - 1)) / 2, वॅल ही प्रत्येक घटकाची वारंवारता असते.
  6. रिटर्न आउटपुट

स्पष्टीकरण

आम्ही एक दिले आहे अॅरे पूर्णांक संख्या दर्शविण्यास सांगितले आहे. अ‍ॅरेमध्ये उपस्थित असलेल्या जोड्या जसे की त्यांचे निर्देशांक समान नसतात परंतु त्या निर्देशांकातील घटक समान असले पाहिजेत. म्हणून आम्ही एक वापरणार आहोत हॅशिंग त्यासाठी. क्रूर शक्ती पध्दतीपेक्षा हॅशिंग हा एक चांगला मार्ग आहे ज्यामध्ये आपल्याला अतिरिक्त वेळ वापरुन त्या सर्व घटकांना भेट द्यावी लागते ओ (एन2). म्हणून आम्ही ते टाळत आहोत.

आम्ही नकाशा घोषित करू, प्रत्येक घटक निवडतो, प्रत्येक घटकाची वारंवारता मोजतो आणि त्यास नकाशात संचयित करतो, जर ते आधीपासूनच नकाशामध्ये अस्तित्त्वात असेल तर त्यासाठी जागा तयार करा, जर ते आधीच अस्तित्वात असेल तर त्याची वारंवारता 1 ने वाढवा.

संयोजन सूत्र वापरण्यासाठी, आम्हाला प्रत्येक संख्येची वारंवारता मोजली पाहिजे. आम्ही अनेक जोड्या निवडणार आहोत जे समान घटकांची दिलेली स्थिती पूर्ण करतात परंतु त्यांचे निर्देशांक नाहीत. आपण असे समजू शकतो की अ‍ॅरे मध्ये उपस्थित असलेली कोणतीही संख्या केटी इंडेक्स पर्यंत कोणत्याही निर्देशांकात के वेळा दर्शविली जाते. नंतर कोणतीही दोन निर्देशांक निवडा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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.