శ్రేణిలో సమాన మూలకాలతో సూచిక జతల సంఖ్య  


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ Atlassian సిటాడెల్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> Intuit స్నాప్డీల్ స్క్వేర్ Yandex
అర్రే హాష్ శోధించండి సార్టింగ్

అనుకుందాం, మేము ఒక ఇచ్చాము పూర్ణ సంఖ్య అమరిక. “శ్రేణిలో సమాన మూలకాలతో సూచిక జతల సంఖ్య” సమస్య సూచికల సంఖ్యను కనుగొనమని అడుగుతుంది (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. ప్రకటించండి a మ్యాప్.
  2. ప్రయాణించండి అమరిక మరియు ప్రతి మూలకం యొక్క ఫ్రీక్వెన్సీని మ్యాప్‌లో లెక్కించండి మరియు నిల్వ చేయండి.
  3. అవుట్పుట్ను 0 కి సెట్ చేయండి.
  4. మ్యాప్‌లో ప్రయాణించి, మ్యాప్ నుండి ప్రతి మూలకం యొక్క ఫ్రీక్వెన్సీని పొందండి.
  5. అవుట్పుట్ చేయండి + = (VAL * (VAL - 1)) / 2, VAL అనేది ప్రతి మూలకం యొక్క పౌన frequency పున్యం.
  6. రిటర్న్ అవుట్పుట్.

వివరణ

మేము ఒక ఇచ్చాము అమరిక పూర్ణాంకాలలో, మొత్తం సంఖ్యను కనుగొనమని మేము కోరాము. వాటి శ్రేణి సూచికలు ఒకేలా ఉండవు కాని ఆ సూచికలలోని అంశాలు ఒకే విధంగా ఉండాలి. కాబట్టి మేము a ను ఉపయోగించబోతున్నాము హ్యాషింగ్ దానికోసం. బ్రూటింగ్ ఫోర్స్ పద్ధతి కంటే హాషింగ్ ఒక మంచి మార్గం, దీనిలో మనం అదనపు సమయాన్ని ఉపయోగించి ఆ మూలకాలన్నింటినీ సందర్శించాలి పై2). కాబట్టి మేము దానిని తప్పించుకుంటున్నాము.

మేము ఒక మ్యాప్‌ను ప్రకటిస్తాము, ప్రతి మూలకాన్ని ఎంచుకొని, ప్రతి మూలకం యొక్క ఫ్రీక్వెన్సీని మ్యాప్‌లోకి లెక్కించి, నిల్వ చేస్తాము, ఇది ఇప్పటికే మ్యాప్‌లో ఉంటే, దాని కోసం ఒక స్థలాన్ని తయారు చేయండి, అది ఇప్పటికే ఉంటే దాని ఫ్రీక్వెన్సీని 1 పెంచండి.

ఇది కూడ చూడు
పెయిర్స్ లీట్‌కోడ్ సొల్యూషన్స్‌లో నోడ్‌లను మార్చుకోండి

కలయిక సూత్రాన్ని ఉపయోగించడానికి, మేము ప్రతి సంఖ్య యొక్క ఫ్రీక్వెన్సీని లెక్కించాలి. సమాన మూలకాల యొక్క ఇచ్చిన పరిస్థితిని సంతృప్తిపరిచే అనేక జతలను మేము ఎంచుకోబోతున్నాము కాని వాటి సూచికలు కాదు. శ్రేణిలో ఉన్న ఏ సంఖ్య అయినా k వ సూచిక వరకు ఏదైనా సూచికలో k సార్లు కనిపిస్తుంది అని మనం అనుకోవచ్చు. అప్పుడు ఏదైనా రెండు సూచికలను ఎంచుకోండి ai మరియు ఒకy ఇది 1 జతగా లెక్కించబడుతుంది. అదేవిధంగా, ay మరియు ఒకx జత కావచ్చు. కాబట్టి, nC2 జతల సంఖ్యను కనుగొనటానికి సూత్రం, దీని కోసం ar [i] = arr [j] కూడా x కి సమానం.

శ్రేణి యొక్క ట్రావెర్సల్ తరువాత, మరియు ప్రతి మూలకాన్ని మరియు దాని సంభవించిన పటాన్ని ఒక మ్యాప్‌లో ఉంచిన తరువాత, మేము మ్యాప్‌లో ప్రయాణించి, మూలకం యొక్క ప్రతి పౌన frequency పున్యాన్ని ఎంచుకొని దానిపై ఒక సూత్రాన్ని వర్తింపజేస్తాము, అవుట్‌పుట్‌తో జోడించి దాన్ని అవుట్‌పుట్‌లో నిల్వ చేస్తాము. మేము అన్ని మూలకాలను మరియు వాటి పౌన encies పున్యాలను దాటి, దానిపై ఆపరేషన్ చేసే వరకు దాన్ని పునరావృతం చేయాలి. చివరికి, మేము ఆ అవుట్పుట్ను తిరిగి ఇస్తాము.

శ్రేణిలో సమాన మూలకాలతో సూచిక జతల సంఖ్యను కనుగొనడానికి సి ++ కోడ్  

#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” శ్రేణిలోని మూలకాల సంఖ్య.