අරාවෙහි සමාන මූලද්‍රව්‍ය සහිත දර්ශක යුගල ගණන


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් ඇට්ලසියන් සිටඩෙල් ෆේස්බුක් ඉන්ටයිට් Snapdeal වර්ග Yandex
අරා හැෂ් සෙවීම් වර්ග කිරීම

අපි අ නිඛිල අරාව. “අරාවෙහි සමාන මූලද්‍රව්‍යයන් සහිත දර්ශක යුගල ගණන” ගැටළුව දර්ශක යුගලයක් සොයා ගැනීමට අසයි (i, ජේ) ඒ විදියට 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. ප්‍රතිදානය නැවත ලබා දෙන්න.

පැහැදිලි කිරීම

අපි ලබා දී ඇත අරාව පූර්ණ සංඛ්‍යා වලින්, මුළු අංකය සොයා ගැනීමට අපි ඉල්ලා සිටිමු. අරාවෙහි ඇති යුගලවල දර්ශක සමාන නොවන නමුත් එම දර්ශකවල මූලද්‍රව්‍ය සමාන විය යුතුය. එබැවින් අපි භාවිතා කිරීමට යන්නේ a හැෂිං ඒ සඳහා. තිරිංග බල ක්‍රමයට වඩා හොඳ ක්‍රමයක් නම්, අමතර කාලය භාවිතා කරමින් එම සියලු අංග වෙත අප පිවිසිය යුතුය මත2). එබැවින් අපි එය වළක්වා ගනිමු.

අපි සිතියමක් ප්‍රකාශයට පත් කරන්නෙමු, එක් එක් මූලද්‍රව්‍යය තෝරාගෙන, එක් එක් මූලද්‍රව්‍යයේ සංඛ්‍යාතය සිතියම තුළට ගණනය කර ගබඩා කර තබන්නෙමු, එය දැනටමත් සිතියමෙහි තිබේ නම්, ඒ සඳහා ස්ථානයක් සාදන්න, එය ඉදිරිපත් කරන්නේ නම් දැනටමත් එහි සංඛ්‍යාතය 1 කින් වැඩි කරන්න.

සංයෝජන සූත්‍රයක් භාවිතා කිරීම සඳහා, අපි එක් එක් සංඛ්‍යාවේ සංඛ්‍යාතය ගණනය කළ යුතුය. සමාන මූලද්‍රව්‍යවල දී ඇති තත්ත්වය සපුරාලන නමුත් ඒවායේ දර්ශක නොවන යුගල කිහිපයක් අපි තෝරා ගන්නෙමු. අරාවෙහි ඇති ඕනෑම සංඛ්‍යාවක් kth දර්ශකය දක්වා ඕනෑම දර්ශකයක k වාරයක් දිස්වන බව අපට උපකල්පනය කළ හැකිය. ඉන්පසු ඕනෑම දර්ශක දෙකක් තෝරන්න ai සහ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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.