ஒரு வரிசையில் சம உறுப்புகளைக் கொண்ட குறியீட்டு ஜோடிகளின் எண்ணிக்கை


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் அட்லாசியன் சிட்டாடல் பேஸ்புக் intuit Snapdeal சதுக்கத்தில் யாண்டேக்ஸ்
அணி ஹாஷ் தேடி வரிசையாக்க

நாம் ஒரு கொடுத்திருக்கிறோம் என்று வைத்துக்கொள்வோம் முழு வரிசை. “ஒரு வரிசையில் சமமான கூறுகளைக் கொண்ட குறியீட்டு ஜோடிகளின் எண்ணிக்கை” என்ற சிக்கல் ஜோடி குறியீடுகளின் எண்ணிக்கையைக் கண்டுபிடிக்கக் கேட்கிறது (i, j) அந்த வகையில் arr [i] = arr [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. வெளியீடு + = (VAL * (VAL - 1)) / 2, VAL என்பது ஒவ்வொரு தனிமத்தின் அதிர்வெண்.
  6. வெளியீடு திரும்பவும்.

விளக்கம்

நாங்கள் ஒரு கொடுத்துள்ளோம் வரிசை முழு எண்களில், மொத்த எண்ணிக்கையைக் கண்டுபிடிக்க நாங்கள் கேட்டுள்ளோம். ஒரு வரிசையில் இருக்கும் ஜோடிகளின் குறியீடுகள் ஒரே மாதிரியாக இல்லை, ஆனால் அந்த குறியீடுகளில் உள்ள கூறுகள் ஒரே மாதிரியாக இருக்க வேண்டும். எனவே நாம் ஒரு பயன்படுத்தப் போகிறோம் ஹேஷிங் இதற்காக. கூடுதல் நேரத்தைப் பயன்படுத்தி அந்த உறுப்புகள் அனைத்தையும் நாம் பார்வையிட வேண்டிய முரட்டு விசை முறையை விட ஹேஷிங் ஒரு சிறந்த வழியாகும் ஓ (என்2). எனவே நாங்கள் அதைத் தவிர்க்கிறோம்.

நாங்கள் ஒரு வரைபடத்தை அறிவிப்போம், ஒவ்வொரு உறுப்புகளையும் எடுத்துக்கொள்வோம், ஒவ்வொரு உறுப்புகளின் அதிர்வெண்ணையும் வரைபடத்தில் எண்ணி சேமித்து வைப்போம், அது ஏற்கனவே வரைபடத்தில் இருந்தால், அதற்கான இடத்தை உருவாக்குங்கள், அது இருந்தால் ஏற்கனவே அதன் அதிர்வெண்ணை 1 ஆல் அதிகரிக்கும்.

சேர்க்கை சூத்திரத்தைப் பயன்படுத்த, ஒவ்வொரு எண்ணின் அதிர்வெண்ணையும் நாம் எண்ண வேண்டும். சம உறுப்புகளின் கொடுக்கப்பட்ட நிலையை பூர்த்தி செய்யும் பல ஜோடிகளை நாங்கள் தேர்ந்தெடுக்கப் போகிறோம், ஆனால் அவற்றின் குறியீடுகள் அல்ல. ஒரு வரிசையில் இருக்கும் எந்த எண்ணும் kth குறியீட்டு வரை எந்த குறியீட்டிலும் k முறை தோன்றும் என்று நாம் கருதலாம். எந்த இரண்டு குறியீடுகளையும் தேர்ந்தெடுக்கவும் ai மற்றும் ஒருy இது 1 ஜோடியாக கணக்கிடப்படும். இதேபோல், அy மற்றும் ஒருx ஜோடியாகவும் இருக்கலாம். அதனால், nC2 ஜோடிகளின் எண்ணிக்கையைக் கண்டுபிடிப்பதற்கான சூத்திரம், இது arr [i] = arr [j] மேலும் 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” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.

விண்வெளி சிக்கலானது

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.