एक सरणी में समान तत्वों के साथ सूचकांक जोड़े की गणना


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना Atlassian गढ़ Facebook सहज स्नैपडील चौकोर Yandex
ऐरे हैश खोजना छंटाई

मान लीजिए, हमने ए पूर्णांक सरणी। समस्या "एक सरणी में समान तत्वों के साथ सूचकांक जोड़े की गणना" सूचकांकों की जोड़ी की संख्या का पता लगाने के लिए कहता है (औरi, j) इस तरह से कि गिरफ्तारी [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. क्या आउटपुट + = (वैल * (वैल - 1)) / 2, वैल प्रत्येक तत्व की आवृत्ति है।
  6. वापसी आउटपुट।

व्याख्या

हमने ए सरणी पूर्णांक की, हमने कुल संख्या का पता लगाने के लिए कहा है। किसी सरणी में मौजूद युग्मों का ऐसा होना कि उनके सूचक समान नहीं हैं, लेकिन उन सूचकांकों के तत्व समान होने चाहिए। इसलिए हम एक का उपयोग करने जा रहे हैं hashing इसके लिए। हास्टिंग बल विधि की तुलना में हैशिंग एक बेहतर तरीका है जिसमें हमें अतिरिक्त समय का उपयोग करके उन सभी तत्वों का दौरा करना पड़ता है पर2)। इसलिए हम इससे बच रहे हैं।

हम प्रत्येक तत्व को उठाते हुए एक नक्शा घोषित करेंगे, प्रत्येक तत्व की आवृत्ति को गिनेंगे और उसे स्टोर करेंगे, अगर यह पहले से ही नक्शे में मौजूद है, तो इसके लिए जगह बनाएं, अगर यह पहले से ही मौजूद है तो इसकी आवृत्ति को 1 से बढ़ा दें।

संयोजन सूत्र का उपयोग करने के लिए, हमें प्रत्येक संख्या की आवृत्ति को गिनना होगा। हम कई जोड़े का चयन करने जा रहे हैं जो समान तत्वों की दी गई स्थिति को संतुष्ट करते हैं लेकिन उनके सूचकांकों को नहीं। हम यह मान सकते हैं कि कोई भी संख्या जो किसी सरणी में मौजूद है, kth इंडेक्स तक किसी भी इंडेक्स में k गुना दिखाई देती है। फिर किसी भी दो सूचकांक चुनें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

जावा कोड एक सरणी में समान तत्वों के साथ सूचकांक जोड़े की गिनती खोजने के लिए

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" सरणी में तत्वों की संख्या है।