صف میں برابر عناصر کے ساتھ انڈیکس جوڑے کی گنتی  


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایمیزون اٹلی درگ فیس بک Intuit Snapdeal چوک Yandex
لڑی ہیش تلاش چھانٹ

فرض کریں ، ہم نے ایک دیا ہے عددی صف. مسئلہ "ایک صف میں برابر عناصر کے ساتھ انڈیکس جوڑے کی تعداد" اشاریہ جات کی جوڑی کی تعداد معلوم کرنے کے لئے پوچھتی ہے (میں ، جے) اس طرح سے ارر [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. اعلان a نقشہ.
  2. سے تجاوز کریں صف اور نقشے میں ہر عنصر کی تعدد گنیں اور اسٹور کریں۔
  3. آؤٹ پٹ کو 0 پر سیٹ کریں۔
  4. نقشہ کو عبور کریں اور نقشہ سے ہر عنصر کی تعدد حاصل کریں۔
  5. آؤٹ پٹ + = (VAL * (VAL - 1)) / 2 ، VAL ہر عنصر کی تعدد ہے۔
  6. واپسی کی واپسی

وضاحت

ہم نے ایک دیا ہے صف انٹیجرز کے ، ہم نے کل نمبر تلاش کرنے کے لئے کہا ہے۔ کسی جوڑ میں جوڑے موجود ہوں جیسے ان کے اشاریے ایک جیسے نہیں ہوتے ہیں بلکہ ان اشاریوں میں موجود عناصر ایک جیسے ہوتے ہیں۔ تو ہم ایک استعمال کرنے کے لئے جا رہے ہیں ہیکنگ اس کے لئے. جانوروں کی طاقت کے طریقہ کار سے کہیں زیادہ فاش کرنا ہیشنگ ہے جس میں ہمیں اضافی وقت کا استعمال کرتے ہوئے ان تمام عناصر کا دورہ کرنا پڑتا ہے O (n)2). تو ہم اس سے گریز کر رہے ہیں۔

ہم نقشہ کا اعلان کریں گے ، ہر عنصر کو چنیں گے ، نقشے میں ہر عنصر کی تعدد گنیں گے اور ذخیرہ کریں گے ، اگر وہ نقشہ میں پہلے سے موجود ہے تو ، اس کے لئے ایک جگہ بنائیں ، اگر وہ پہلے سے موجود ہے تو اس کی تعدد کو 1 سے بڑھا دے گا۔

یہ بھی دیکھتے ہیں
جوڑیں لیٹکوڈ حل میں نوڈس کو تبدیل کریں

مرکب فارمولہ استعمال کرنے کے ل we ، ہمیں ہر نمبر کی تعدد گننی ہوگی۔ ہم متعدد جوڑے منتخب کرنے جارہے ہیں جو برابر عناصر کی دی گئی شرط کو پورا کرتے ہیں لیکن ان کے اشاریے نہیں۔ ہم فرض کر سکتے ہیں کہ کسی بھی تعداد میں جو صف میں موجود ہے K K انڈیکس تک کسی بھی انڈیکس میں k بار ظاہر ہوتا ہے۔ پھر کوئی دو اشاریہ چنیں ai اور ایکy جس میں 1 جوڑی شمار ہوگی۔ اسی طرح ، ay اور ایکx جوڑا بھی ہوسکتا ہے۔ تو ، nC2 جوڑیوں کی تعداد معلوم کرنے کا فارمولا ہے جس کے لئے ارر [i] = ارر [ج] بھی 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

پیچیدگی کا تجزیہ  

وقت کی پیچیدگی

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔

یہ بھی دیکھتے ہیں
Iterative پیشگی ٹروراسال

خلائی پیچیدگی

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔