Өгөгдсөн тоотой тэнцүү бүтээгдэхүүнтэй гурван ихрийн тоог тоолох  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Accolite Амазоны Cisco Flipkart Кулиза Publicis Sapient
Array Хаш Хоёр заагч

“Өгөгдсөн тоотой тэнцүү бүтээгдэхүүнтэй гурвалсан гурвын тоог тоолох” гэсэн бодлогод бидэнд бүхэл тоон массив ба тоо өгөгдсөн болно m. Асуудлын шийдэл нь m-тэй тэнцүү бүтээгдэхүүнтэй гурвалсан гурвын тоог олохыг хүсч байна.

Жишээ нь  

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

Тайлбар

M-тэй тэнцүү бүтээгдэхүүн үүсгэсэн гурван ихэр нь (1,5,6), (5,2,3) ба (1,3,10)

Өгөгдсөн тоотой тэнцүү бүтээгдэхүүнтэй гурван ихрийн тоог тоолохPin

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

Тайлбар

M-тэй тэнцүү бүтээгдэхүүн үүссэн гурван ихэр нь (2,1,10), (4,5,1)

Алгоритм  

  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 тоотой тэнцүү байх гурван ихрийг олох явдал юм. Энэ асуултыг шийдэхийн тулд бид гэнэн хандлагыг ашиглахгүй, энэ нь бидэнд илүү их цаг хугацаа шаардагдана. Гурвалсан элемент бүрийг сонгоход зочлохын оронд бид ашиглах болно Хаширч байна.

мөн үзнэ үү
Примийн алгоритм

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

Массивыг туулсны дараа бид hashmap дахь утгуудтай болно. Гаралтын утгыг 0 болгож тохируул. Одоо бид үүрлэсэн гогцоо ашиглах болно. Үүний дотор бид гаднах гогцоонд элемент авч, дараагийн гогцоонд өөр нэг элементийг сонгоно. Дараа нь бид гуравдахь элементийг олж мэдэх болно. Гурав дахь элементийг олоход 'if оператор' гэсэн бүх нөхцлийг ашигладаг. Arr [i] * arr [j] хийсний дараа бидний олох ёстой зүйл бол гуравдахь элемент юм. Тиймээс энгийн тэмдэглэл дээр хэрэв a * 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-ийг ашигласан тул. Тиймээс энэ хайлтын ажиллагааг O (1) дэх HashMap-ээр өмнө нь O (N) цаг үед гэнэн байдлаар хийж байсан болно. Тиймээс энэхүү хурд нь HashMap-тэй холбоотой юм.

мөн үзнэ үү
Ажилтан бүрийн дор ажиллагсдын тоог олох

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" нь массив дахь элементүүдийн тоо юм. Учир нь бид бүх элементүүдийг газрын зураг дээр хадгалах болно. Сансрын нарийн төвөгтэй байдал нь шугаман хэлбэртэй байдаг.