Массивде бар буюмдар бар Жуптарды эсептөө


Кыйынчылык деңгээли жеңил
Көп суралган Accolite Amazon Кара таш Moonfrog Labs Ola Cabs снэпчат Xome
согуштук тизме таштанды

Массив көйгөйүндө өнүмдөрү бар эсептөө жуптарында биз ан согуштук тизме, продуктунун мааниси массивде болгон баардык так жуптарды санап чыгыңыз.

мисал

кирүү

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

продукция

Продукциясы массивде болгон так жуптардын саны: 2

Жуптар: (2, 3), (5, 3)

Brute force: Массивде продукт бар болгон Count Pairs үчүн 1-ыкма

Бардык түгөйлөрдү кайталап, андан кийин ал элементтин массивде бар же жок экендигин текшериңиз. Эгер ал бар болсо, анда жоопту 1ге көбөйтүңүз.

Algorithm

  1. 0 өзгөрмөсү менен ans өзгөрмөсүн баштаңыз.
  2. 0 үчүн n-1 диапазонунда I үчүн цикл иштетүү;
    1. J үчүн циклди i + 1 ден n-1 диапазонунда иштетүү
      1. Эми, 0 ден n-1 диапазонуна чейин k үчүн цикл иштетүү
        1. Эгерде A [i] * A [j] A [k] га барабар болсо, анда ans-ты 1ге көбөйтүп, циклден үзгүлтүккө учурат.
      2. Ans басып чыгар.

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).

Хэшинг колдонуу: 2-ыкма, массивинде продукт бар граф жуптарга

Негизги идея

Массивдин бардык элементтерин таштанды таблицасында көрөбүз. Андан кийин, эгер жуптардын продуктусу массивде бар болсо, анда биз бардык жуптарды кайталайбыз, андан кийин жообун 1ге көбөйтүп алабыз. Товардын массивде бар же жок экендигин хэш-таблицадан туруктуу убакытта издөө менен текшере алабыз.

Algorithm

  1. Хэш таблицасын жарыялаңыз.
  2. Ans деген өзгөрмө инициализациялап, жоопту сактайт.
  3. 0 үчүн n-1 диапазонунда I үчүн цикл иштетүү.
    1. J үчүн циклди j + 1ден n-1ге чейин иштетүү;
      1. Эгерде хэш-таблицада A [i] жана A [j] көбөйтүндүлөрү бар болсо, анда анс-ты 1ге көбөйтүңүз.
    2. Ans басып чыгар.

Мисалы:

Массив үчүн [] = {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).

шилтемелер