एर्रेमा समान तत्वहरूको साथ अनुक्रमणिका जोडीहरूको गणना


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन Atlassian Citadel फेसबुक Intuit स्नैपडल स्क्वायर Yandex
एरे हैश खोजी क्रमबद्ध

मानौं, हामीले एउटा दिएका छौं पूर्णांक array। समस्या "एरेमा बराबर तत्वहरूको साथ अनुक्रमणिका जोडीहरूको गणना" सूचकांकको जोडीको संख्या फेला पार्नको लागि सोध्छ (i, j) त्यस्तो तरिकामा एर [i] = एर [j]i सँग बराबर छैन j.

उदाहरणका

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

स्पष्टीकरण

सूचकांकका जोडीहरू: (०,)), (१,)), (२,))

एर्रेमा समान तत्वहरूको साथ अनुक्रमणिका जोडीहरूको गणना

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

स्पष्टीकरण

सूचकांकका जोडीहरू: (०, १)

अल्गोरिदम

  1. घोषणा गर्नुहोस् नक्सा.
  2. पार गर्नुहोस् array र नक्सामा प्रत्येक तत्वको फ्रिक्वेन्सी गणना गर्नुहोस्।
  3. ० मा आउटपुट सेट गर्नुहोस्।
  4. नक्सालाई ट्र्याभर गर्नुहोस् र नक्साबाट प्रत्येक तत्वको फ्रिक्वेन्सी प्राप्त गर्नुहोस्।
  5. आउटपुट गर्नुहोस् + = (VAL * (VAL - १)) / २, VAL प्रत्येक तत्वको फ्रिक्वेन्सी हो।
  6. फिर्ता आउटपुट

स्पष्टीकरण

हामीले एउटा दिएका छौं array पूर्णांकहरूको, हामीले कुल संख्या पत्ता लगाउन सोध्यौं। एर्रेमा उपस्थित जोडीहरू जस्तो कि उनीहरूको सूचकहरू उस्तै हुँदैनन् तर ती सूचकांकहरूमा तत्त्वहरू समान हुनुपर्दछ। त्यसैले हामी एक प्रयोग जाँदैछन् ह्याशिंग यसको लागी। ह्याशिंग एउटा क्रुर बल विधि भन्दा उत्तम तरिका हो जसमा हामीले ती सबै तत्वहरूको भ्रमण गर्नुपर्दछ अतिरिक्त समयको प्रयोग गरेर O (n)2)। त्यसैले हामी त्यसलाई बेवास्ता गरिरहेका छौं।

हामी मानचित्र घोषित गर्नेछौं, प्रत्येक तत्व लाई उठाउँदै, नक्सामा प्रत्येक तत्वको फ्रिक्वेन्सी गणना र भण्डार गर्नुहोस्, यदि यो नक्सामा पहिले नै अवस्थित छ भने, यसको लागि स्थान बनाउँनुहोस्, यदि यो पहिले नै बस १ ले यसको फ्रिक्वेन्सी बढाउँदछ।

संयोजन सूत्र प्रयोग गर्न, हामीले प्रत्येक नम्बरको फ्रिक्वेन्सी गणना गर्नुपर्दछ। हामी धेरै जोडीहरू चयन गर्न गइरहेका छौं जसले बराबर तत्त्वहरूको शर्त पूरा गर्दछ तर उनीहरूको सूचकांकहरू होइन। हामी मान्न सक्छौं कि कुनै पनि संख्या जुन एर्रेमा रहेको छ केटी सूचकांकमा कुनै पनि सूचकांकमा k पटक देखा पर्छ। त्यसो भए कुनै दुई सूचकांकहरू लिनुहोस्i र एकy जुन १ जोडी मानिनेछ। त्यस्तै, एy र एकx जोडी पनि हुन सक्छ। त्यसो भए nC2 जोडीहरूको संख्या पत्ता लगाउनको लागि सूत्र हो जसको लागि अरर [i] = एर [j] पनि x बराबर छ।

एर्रेको traversal पछि, र प्रत्येक तत्व र यसको घटना एक नक्शा मा राख्नु, हामी नक्सा पार गर्न, तत्व को प्रत्येक आवृत्ति लिन्छ र यसमा एक सूत्र लागू, आउटपुट संग जोडेर र आउटपुट मा यो भण्डारण हुनेछ। हामीले यसलाई दोहोर्याइरहनु पर्छ जब सम्म हामी सबै तत्वहरू र उनीहरूको फ्रिक्वेन्सीहरू ट्र्यावर्स हुँदैन र यसमा एउटा अपरेसन प्रदर्शन गर्दैनौं। र अन्त्यमा, हामी त्यो आउटपुट फर्काउँछौं।

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" एर्रेमा एलिमेन्ट्सको संख्या हो।