Берилген санга барабар болгон үчтүктүн санын эсептөө


Кыйынчылык деңгээли орто
Көп суралган Accolite Amazon Cisco Flipkart Кулиза Publicis Sapient
согуштук тизме таштанды Эки көрсөткүч

"Берилген санга барабар көбөйтүмү бар үч эмдин санын эсептөө" маселеси бизге бүтүндөй массив жана сан берилгенин билдирет m. Проблеманын чечими м-ге барабар продукт менен үч эмдин жалпы санын табууну суранат.

мисал

arr[] = {1,5,2,6,10,3}
m=30
3

түшүндүрүү

М-ге барабар өнүмдү түзгөн үч эм (1,5,6), (5,2,3) жана (1,3,10)

Берилген санга барабар болгон үчтүктүн санын эсептөө

arr[] = {2,4,5,1,10}
m=20
2

түшүндүрүү

М-ге барабар өнүм түзгөн үч эм (2,1,10), (4,5,1)

Algorithm

  1. Декларация a карта.
  2. Ар бир элементтин индексин картага өтүп, сактаңыз согуштук тизме.
  3. Чыгууну 0 деп койду.
  4. Ички циклди колдонуп, массивди дагы бир жолу айланып өтүү:
    1. ((Arr [i] * arr [j] <= m) && (arr [i] * arr [j]! = 0) && (m% (arr [i] * arr [j]) == 0 экендигин текшерүү )).
      1. Эгер бул чын деп табылса, анда m / (arr [i] * arr [j]) таап, картадан издеңиз.
    2. Ошондой эле, биз тапкан үчүнчү элемент учурдагы эки элементке (arr [i] жана arr [j]) барабар эмес экендигин текшериңиз.
      1. Эгер шарт канааттандырылса, анда чыгарылган продукциянын санын 1ге көбөйтүңүз.
  5. Чыгууну кайтаруу.

түшүндүрүү

Биздин милдет - үчтүктү табуу, алардын продуктусу берилген m санына барабар болушу керек. Бул суроону чечүү үчүн биз ишенчээк мамилени колдонбойбуз, бул бизге көбүрөөк убакытты талап кылат. Үч эмдин ар бир элементин чогултууга барганга караганда, биз колдонобуз Hashing.

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

Массивди кесип өткөндөн кийин, бизде хэшмаптагы маанилер бар. Чыгуунун маанисин 0 деп коюңуз, эми биз уяланган циклди колдонобуз. Андан сырткы циклдеги элементти алсак, кийинки циклден дагы бир элементти тандап алабыз. Андан кийин үчүнчү элементти аныктайбыз. 'If операторунда' турган бардык шарттар үчүнчү элементти табуу үчүн колдонулат. Arr [i] * arr [j] жасагандан кийин биз үчүнчү элементти гана табышыбыз керек. Ошентип, жөнөкөй нотада, эгерде * b * c = m ⇒, анда c = m / a * b.

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

Берилген санга барабар чыгарылган үч эмдин санын эсептөө үчүн C ++ коду

#include<iostream>
#include<unordered_map>
using namespace std;

int getProductTriplets(int arr[], int n, int m)
{
    unordered_map<int, int> numindex;
    for (int i = 0; i < n; i++)
        numindex[arr[i]] = i;

    int output = 0;

    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if ((arr[i] * arr[j] <= m) && (arr[i] * arr[j] != 0) && (m % (arr[i] * arr[j]) == 0))
            {
                int third = m / (arr[i] * arr[j]);
                auto it = numindex.find(third);

                if (third != arr[i] && third != arr[j]&& it != numindex.end() && it->second > i&& it->second > j)
                    output++;
            }
        }
    }
    return output;
}
int main()
{
    int arr[] = {1,5,2,6,10,3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 30;

    cout <<"Total product triplets are: "<<getProductTriplets(arr, n, m);
    return 0;
}
Total product triplets are: 3

Берилген санга барабар продукт менен үч эмдин санын эсептөө үчүн Java коду

import java.util.HashMap;

class TripletProductPair
{
    public static int getProductTriplets(int arr[], int n, int m)
    {
        HashMap<Integer, Integer> numindex = new HashMap<Integer, Integer>(n);
        for (int i = 0; i < n; i++)
            numindex.put(arr[i], i);

        int output = 0;
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {

                if ((arr[i] * arr[j] <= m) && (arr[i] * arr[j] != 0) && (m % (arr[i] * arr[j]) == 0))
                {
                    int third = m / (arr[i] * arr[j]);

                    numindex.containsKey(third);
                    if (third != arr[i] && third != arr[j]&& numindex.containsKey(third) && numindex.get(third) > i && numindex.get(third) > j)
                    {
                        output++;
                    }
                }
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,5,2,6,10,3};
        int m = 30;
        System.out.println("Total product triplets are: "+getProductTriplets(arr, arr.length, m));
    }
}
Total product triplets are: 3

Комплекстик анализ

Убакыт татаалдыгы

O (n2кайда "N" массивдеги элементтердин саны. Эки уяны колдонуп, үчүнчү элементти издөө үчүн Hashmap колдондук. Ошентип, бул издөө иш-аракетин H (M) O (1) ичинде жүргүзүп жатабыз, ал буга чейин O (N) убагында аң-сезимсиз мамиле кылган. Ошентип, мындай ылдамдык HashMap менен байланыштуу.

Космостун татаалдыгы

O (N) кайда "N" массивдеги элементтердин саны. Анткени биз бардык элементтерди картада сактайбыз. Космостун татаалдыгы сызыктуу.