একটি অ্যারেতে সমান উপাদানগুলির সাথে সূচী জোড়ার সংখ্যা


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক Atlassian দুর্গ ফেসবুক যুক্তি তর্ক Snapdeal বর্গক্ষেত্র ইয়ানডেক্স
বিন্যাস কাটা খোঁজ শ্রেণীবিভাজন

ধরুন, আমরা একটি দিয়েছি পূর্ণসংখ্যা বিন্যাস। সমস্যাটি "অ্যারেতে সমান উপাদানগুলির সাথে সূচকের জোড়গুলির গণনা" সূচকগুলির জোড়ার সংখ্যাটি খুঁজে পেতে জিজ্ঞাসা করে (i, 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. আউটপুট করুন + = (ভ্যাল * (ভ্যাল - 1)) / 2, ভ্যাল হ'ল প্রতিটি উপাদানের ফ্রিকোয়েন্সি।
  6. রিটার্ন আউটপুট।

ব্যাখ্যা

আমরা একটি দিয়েছি বিন্যাস পূর্ণসংখ্যার, আমরা মোট সংখ্যাটি খুঁজে বের করতে বলেছি। একটি অ্যারেতে উপস্থিত এমন জোড়গুলির যাতে তাদের সূচকগুলি একই হয় না তবে সেই সূচকের উপাদানগুলি একই হওয়া উচিত। সুতরাং আমরা একটি ব্যবহার করতে যাচ্ছি হ্যাশ এর জন্য. ব্রাশ ফোর্স পদ্ধতির চেয়ে হ্যাশিং একটি ভাল উপায় যেখানে অতিরিক্ত সময় ব্যবহার করে আমাদের সেই সমস্ত উপাদানগুলিতে যেতে হবে চালু2)। তাই আমরা তা এড়িয়ে চলেছি।

আমরা একটি মানচিত্র ঘোষণা করব, প্রতিটি উপাদান বাছাই করব, মানকের প্রতিটি উপাদানটির ফ্রিকোয়েন্সি গণনা করব এবং সংরক্ষণ করব, যদি এটি মানচিত্রে ইতিমধ্যে উপস্থিত থাকে তবে এটির জন্য একটি জায়গা তৈরি করুন, যদি এটি ইতিমধ্যে উপস্থিত থাকে তবে কেবল তার ফ্রিকোয়েন্সিটি 1 দ্বারা বাড়িয়ে তুলবে।

একটি সংমিশ্রণ সূত্র ব্যবহার করতে, আমাদের প্রতিটি সংখ্যার ফ্রিকোয়েন্সি গণনা করতে হবে। আমরা বেশ কয়েকটি জুড়ি নির্বাচন করতে যাচ্ছি যা সমান উপাদানের প্রদত্ত শর্ত পূরণ করে তবে তাদের সূচকগুলি নয়। আমরা ধরে নিতে পারি যে অ্যারেতে উপস্থিত যে কোনও সংখ্যা কেএথ সূচক পর্যন্ত কোনও সূচীতে কে বার প্রদর্শিত হয়। তারপরে যেকোন দুটি সূচক বেছে নিন ai এবং একটিy যা 1 জোড়া হিসাবে গণনা করা হবে। একইভাবে, কy এবং একটিx জোড়াও হতে পারে। সুতরাং, nC2 জোড়গুলির সংখ্যা অনুসন্ধানের সূত্র হ'ল যার জন্য আরআর [i] = আরার [জে] এছাড়াও 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

জটিলতা বিশ্লেষণ

সময় জটিলতা

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।

স্পেস জটিলতা ity

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।