قطار ۾ برابر عناصر سان انڊيڪس جوڙن جو تعداد


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Amazon Atlassian قلعي ڪريو سائنسي اسپيڊل چورس ياندڪس
ڪيريو هاش ڳولها ترتيب ڏيڻ

فرض ڪريو ، اسان هڪ ڏنو آهي انٽرويو صف. مسئلو ”انڊيڪس جوڙن کي هڪ جيتري برابر عنصرن سان گڏ” ڳڻپ لاءِ پڇي ٿو ته اشاري جو جوڙو نمبر (مان ، جي) اهڙي طريقي سان arr [i] = arr [جي] ۽ 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 ذريعي وڌايو.

هڪ گڏيل فارمولا استعمال ڪرڻ لاءِ ، اسان کي هر نمبر جي فريڪوئنسي جي ڳڻپ ڪرڻو آهي. اسان ڪيترن ئي جوڙن کي چونڊڻ وارا آهيون جيڪي برابر عنصرن جي ڏنل حالت کي مطمئن ڪن ٿا پر انهن جا اشارا نه. اسان اهو فرض ڪري سگهون ٿا ته ڪي به نمبر جيڪو صف ۾ موجود آهي ، ڪي انڊيڪس تائين ڪي انڊيڪس ۾ ظاهر ٿئي ٿو. پوءِ ٻه ٻه اشارا چونڊيوi ۽ هڪy جنهن کي 1 جوڙي ڳڻيو ويندو. ساڳي طرح ، هڪy ۽ هڪx جوڙي به سگھي ٿو. تنهن ڪري ، nC2 جوڙن جي تعداد معلوم ڪرڻ جو فارمولا آهي جنهن لاءِ arr [i] = arr [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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.

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

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.