დაითვალეთ წყვილი, რომელთა პროდუქტები მასივშია


Რთული ტური Easy
ხშირად ეკითხებიან თანამოსაყრელი Amazon BlackRock Moonfrog ლაბორატორიები ოლა კაბინები Snapchat Xome
Array Hash

თვლის წყვილებში, რომელთა პროდუქტები მასივის პრობლემაშია, ჩვენ მივეცით მასივი, დაითვალეთ ყველა მკაფიო წყვილი, რომელთა პროდუქტის ღირებულება მასივშია.

მაგალითი

შეყვანის

A [] = {2, 5, 6, 3, 15}

გამოყვანის

მკაფიო წყვილების რაოდენობა, რომელთა პროდუქტი არსებობს მასივში: 2

წყვილია: (2, 3), (5, 3)

უხეში ძალა: მიდგომა 1-ისთვის Count წყვილებისთვის, რომელთა პროდუქტიც არსებობს

გაიმეორეთ ყველა წყვილი და შემდეგ შეამოწმეთ, არსებობს თუ არა ეს ელემენტი მასივში. თუ ის არსებობს, პასუხი გაზარდეთ 1-ით.

ალგორითმი

  1. ინიცირებადი ცვლადი ans 0-ით.
  2. გაუშვით მარყუჟი I- ის ჩათვლით 0-დან n-1-მდე;
    1. აწარმოეთ მარყუჟი j- ზე i + 1-დან n-1 დიაპაზონში
      1. ახლა, აწარმოეთ მარყუჟი k- სთვის 0-დან n-1-მდე
        1. თუ A [i] * A [j] უდრის A [k] - ს, მაშინ ans- ები 1-ით გაზარდა და გამოიყოფა მარყუჟიდან.
      2. დაბეჭდე ანს.

C ++ პროგრამა

#include <bits/stdc++.h>
using namespace std;
void countPairs(vector<int> &A)
{
    int n = A.size();
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                if (A[i] * A[j] == A[k])
                {
                    ans++;
                    break;
                }
            }
        }
    }
    cout << "Number of distinct pairs whose product exists in array is: " << ans << endl;
    return;
}
int main()
{
    vector<int> A = {2, 5, 6, 3, 15, 30};
    countPairs(A);
    return 0;
}
Number of distinct pairs whose product exists in array is: 4

JAVA პროგრამა

public class Main
{
    static void countPairs(int[] A)
    {
        int n = A.length;
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                for (int k = 0; k < n; k++)
                {
                    if (A[i] * A[j] == A[k])
                    {
                        ans++;
                        break;
                    }
                }
            }
        }
        System.out.print("Number of distinct pairs whose product exists in array is: "+ans);
    }
  public static void main(String[] args) {
    int[] A={2, 5, 6, 3, 15, 30};
    countPairs(A);
  }
}
Number of distinct pairs whose product exists in array is: 4

სირთულის ანალიზი გრაფი წყვილებისთვის, რომელთა პროდუქტიც არსებობს

დროის სირთულე: ჩვენ ვიყენებთ სამ ჩასმულ მარყუჟს, ყველა ზომის N. ასე რომ, დროის სირთულეა O (N ^ 3).

სივრცის სირთულე: ჩვენ არ ვიყენებთ რაიმე დამატებით ადგილს, ამიტომ სივრცის სირთულე არის O (1).

Hashing- ის გამოყენება: მიდგომა 2 ჯამური წყვილებისთვის, რომელთა პროდუქტიც არსებობს

Მთავარი იდეა

მასივის ყველა ელემენტს მივცემთ hash ცხრილში. ამის შემდეგ, ჩვენ გავიმეორებთ ყველა წყვილს, თუ წყვილის პროდუქტი არსებობს მასივში, შემდეგ გავზარდოთ პასუხი 1-ით. შეგვიძლია შეამოწმოთ, არის თუ არა პროდუქტი მასივში, თუ არა ჰეშის ცხრილში მუდმივი დროით ძებნით.

ალგორითმი

  1. გამოაცხადეთ ჰეშის მაგიდა.
  2. ინიცირებადი ცვლადი ans 0-ით, რომელიც შეინახავს პასუხს.
  3. გაუშვით I მარყუჟი 0-დან n-1 დიაპაზონში.
    1. აწარმოეთ მარყუჟი j- ისთვის j + 1 დან n-1 დიაპაზონში;
      1. თუ A [i] და A [j] პროდუქტი იმყოფება ჰეშის ცხრილში, მაშინ AN- ები გაზარდეთ 1-ით.
    2. დაბეჭდე ანს.

მაგალითად:

მასივისთვის A [] = {2, 4, 2, 4, 15, 8, 20}

ჰეშის მაგიდა ასე გამოიყურება:

დაითვალეთ წყვილი, რომელთა პროდუქტები მასივშია

C ++ პროგრამა

#include <bits/stdc++.h>
using namespace std;
void countPairs(vector<int> &A)
{
    int n = A.size();
    unordered_set<int> hash_table;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        hash_table.insert(A[i]);
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (hash_table.count(A[i] * A[j]) == 1)
            {
                ans++;
            }
        }
    }
    cout << "Number of distinct pairs whose product exists in array is: " << ans << endl;
    return;
}
int main()
{
    vector<int> A = {2, 4, 2, 4, 15, 30, 8};
    countPairs(A);
    return 0;
}
Number of distinct pairs whose product exists in array is: 7

JAVA პროგრამა

import java.util.*; 
public class Main
{
    static void countPairs(int[] A)
    {
        int n = A.length;
        Set<Integer> hash_table=new HashSet<Integer>();
        int ans = 0;
        for(int i=0;i<n;i++)
        {
            hash_table.add(A[i]);
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if(hash_table.contains(A[i]*A[j])==true)
                {
                    ans++;
                }
            }
        }
        System.out.print("Number of distinct pairs whose product exists in array are: "+ans);
    }
  public static void main(String[] args) {
    int[] A={2, 4, 2, 4, 15, 30, 8};
    countPairs(A);
  }
}
Number of distinct pairs whose product exists in array are: 7

სირთულის ანალიზი გრაფი წყვილებისთვის, რომელთა პროდუქტიც არსებობს

დროის სირთულე: ჩვენ ვიყენებთ ორ ჩადგმულ მარყუჟს, ორივე ზომის N. ასე რომ, დროის სირთულეა O (N ^ 2).

სივრცის სირთულე: ჩვენ ვინახავთ ჰეშის ცხრილს მასივის ელემენტების შესანახად. სივრცის სირთულე არის O (N).

ლიტერატურა