ინდექსური წყვილების მასა თანაბარი ელემენტებით


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Atlassian ციხედ Facebook Intuit Snapdeal Square Yandex
Array Hash Searching დახარისხება

დავუშვათ, ჩვენ მივეცით მთელი რიცხვი მასივი. პრობლემა "მასივში თანაბარი ელემენტების მქონე ინდექსური წყვილების რაოდენობა" ითხოვს ინდექსების წყვილიმე, ჯ) ისე რომ 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. დაბრუნების შედეგი.

განმარტება

ჩვენ მივეცით მასივი მთელი რიცხვებისა, ჩვენ ვთხოვეთ გაერკვია წყვილი მასივში ისეთია, რომ მათი ინდექსები არ არის იგივე, მაგრამ ამ ინდექსების ელემენტები უნდა იყოს იგივე. ჩვენ ვაპირებთ გამოვიყენოთ ა ჰაშინგი ამისთვის. Hashing უკეთესი გზაა, ვიდრე უხეში ძალის მეთოდი, რომელშიც ჩვენ უნდა მოვინახულოთ ყველა ეს ელემენტი დამატებითი დროის გამოყენებით ო (ნ2). ასე რომ, ჩვენ ამას ვერიდებით.

ჩვენ გამოვაცხადებთ რუქას, ავიღებთ თითოეულ ელემენტს, დაითვლით და შევინახავთ თითოეული ელემენტის სიხშირეს რუქაში, თუ ის უკვე რჩება რუქაში, დავაყენებთ ადგილს, თუ ეს უკვე არის, უბრალოდ გავზარდოთ მისი სიხშირე 1-ით.

კომბინირებული ფორმულის გამოსაყენებლად უნდა დავთვალოთ თითოეული რიცხვის სიხშირე. ჩვენ ვაპირებთ შეარჩიოთ რამდენიმე წყვილი, რომლებიც აკმაყოფილებენ მოცემული ტოლი ელემენტების პირობას, მაგრამ არა მათი ინდექსები. შეგვიძლია ვივარაუდოთ, რომ მასივში არსებული ნებისმიერი რიცხვი გამოჩნდება k ჯერ ნებისმიერ ინდექსში, kth ინდექსამდე. შემდეგ აირჩიე ნებისმიერი ორი ინდექსი 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

სირთულის ანალიზი

დროის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.