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


Хэцүү байдлын түвшин Дунд
Байнга асуудаг 24 * 7 инновацийн лаборатори Амазоны Авалара Quora Roblox
Array Хаш Математик

"Өгөгдсөн бүтээгдэхүүнийг хослуулах" гэсэн асуудалд танд бүхэл тоо массив ба "x" тоо. Массив нь өгөгдсөн оролтын массивт 'x' -тэй тэнцүү хос бүтээгдэхүүнээс бүрдэх эсэхийг тодорхойл.

Жишээ нь

[2,30,12,5]
x = 10
Yes, it has Product Pair

Тайлбар

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

Энд 2 ба 5 нь үржвэр нь 10-тай тэнцүү элементүүд юм, өөрөөр хэлбэл, x.

[10,30,12,50]
x = 40
No, it does not have a Product Pair.

Тайлбар

Массив дотор үржвэр нь x өөр, 40-тэй тэнцэх ийм хос байхгүй.

[20,3,12,5]
x = 100
Yes, it has a Product Pair.

Тайлбар

Массив дахь 20 ба 5 нь үржвэр нь x өөрөөр хэлбэл 100-тай тэнцэх хосыг бүрдүүлдэг.

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

  1. Мэдүүлэх a HashSet.
  2. Хэрэв дор хаяж 2 утга өгсөн бол массивын уртыг шалгана уу.
    1. Хэрэв үгүй ​​бол хуурамчаар буцаана уу.
  3. Хэдийгээр би <n.
    1. Массивын элементүүдийн нэг нь 0-тэй тэнцүү байгаа эсэхийг шалгана уу
      1. Хэрэв x-д 0-ийг өгсөн бол буцаад үнэн болно.
    2. X-ийг arr-ийн аль ч элементэд хувааж 0 үлдэгдэл өгөх эсэхийг шалгана уу.
      1. Хэрэв HashSet нь (x / arr [i]) агуулсан бол true гэсэн утгыг буцаана.
      2. Arr [i] -ийг HashSet дээр нэмнэ үү.
  4. Худал буцаах.

Тайлбар

Бидэнд массив ба тоо өгөгдсөн асуудал өгөгдсөн болно. Дараа нь оролтын массив дотор x-тэй тэнцүү Бүтээгдэхүүнтэй хосууд байгаа эсэхийг олж мэдэх ёстой. Бид ашиглах гэж байна хэшээл энэ асуудлыг шийдэх. Тухайн Бүтээгдэхүүн бүхий массивт байгаа утгыг олж мэдэх. Бид x-г arr [i] -ээр хуваагаад үлдсэн хэсэг нь 0-тэй байгаа эсэхийг шалгана. Хэрэв 0 гэж олдсон бол бид HashSet дээр x / arr [i] байгаа эсэхийг шалгана. Хэрэв энэ нь байгаа бол бид үнэн болно. Хэрэв үгүй ​​бол тухайн элементийн массивыг HashSet дээр нэмж цааш нь гүйлгэх боломжтой.

Бидэнд тэг бүтээгдэхүүнийг тодорхой шалгах нөхцөлийг өгсөн. Хэрэв бидний x утга 0 гэж өгөгдсөн бол массивын аль нэг элемент 0 эсэхийг шалгана. Хэрэв тийм бол тэг болно.

Жишээ авч, үүнийг ойлгоорой.

arr [] = {10,20,9,40}, X = 90

i = 0, arr [i] = 10,

Arr [i] нь 0-тэй тэнцүү байгаа эсэхийг бид шалгах болно, гэхдээ энэ массив дотор нэг ч элемент 0 биш тул ямар ч давталтаар гүйцэтгэхгүй.

Хэрэв бид x% arr [i] = = 0 өнгөрвөл бид үүнийг шалгах болно, дараа нь x / arr [i] олонлогт байгаа эсэхийг шалгана.

90% 10 == 0 үнэн бөгөөд 90/10 = 9 нь HashSet дээр хараахан ороогүй байна.

Тиймээс бид arr [i] = 10-ийг олонлогт нэмэх болно.

90% 20 == 0 нь худлаа бөгөөд юу ч болохгүй

90% 9 == 0 үнэн бөгөөд 90/9 = 10 нь HashSet дээр бид аль хэдийн оруулсан шиг HashSet дээр байдаг.

Тиймээс бид 9 ба 10 гэсэн массивын Бүтээгдэхүүний хосыг буцааж, үнэнийг буцааж хэвлэнэ гэсэн үг юм

Гаралт: "Тийм ээ, энэ нь бүтээгдэхүүний хослолтой".

Өгөгдсөн бүтээгдэхүүнтэй хосыг хайж олох C ++ код

#include<iostream>
#include<unordered_set>
using namespace std;
bool getProduct (int arr[], int n, int x)
{
  if (n < 2)
    return false;

  unordered_set<int> s;

  for (int i=0; i<n; i++)
  {
    if (arr[i] == 0)
    {
    if (x == 0)
      return true;
    else
      continue;
    }
    if (x%arr[i] == 0)
    {
      if (s.find(x/arr[i]) != s.end())
                return true;

      s.insert(arr[i]);
    }
  }
  return false;
}
int main()
{
  int arr[] = {10, 20, 9, 40};
  int x = 90;
  int n = sizeof(arr)/sizeof(arr[0]);
  getProduct (arr, n, x)? cout << "Yes, it has Product Pair\n":cout << "No, it does not have Product Pair";
  return 0;
}
Yes, it has Product Pair

Өгөгдсөн бүтээгдэхүүнтэй хослуулахын тулд Java код

import java.util.HashSet;

class pairX
{
    public static boolean getProduct (int arr[], int n, int x)
    {
        HashSet<Integer> mySet = new HashSet<>();

        if(n < 2)
            return false;

        for(int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
            {
                if(x == 0)
                    return true;
                else
                    continue;
            }
            if(x % arr[i] == 0)
            {
                if(mySet.contains(x / arr[i]))
                    return true;

                mySet.add(arr[i]);
            }
        }
        return false;
    }
    public static void main(String[] args)
    {
        int arr[] = {10, 20, 9, 40};
        int x = 90;
        int n = arr.length;

        if(getProduct (arr, n, x))
            System.out.println("Yes, it has Product Pair");
        else
            System.out.println("No, it does not have Product Pair");
    }
}
Yes, it has Product Pair

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N) хаана "N" массив дахь элементүүдийн тоо юм. Бид HashSet-ийг ашиглаж байсан тул O (1) хугацаанд оруулах, устгах, хайлт хийх боломжтой болсон. Үүний ачаар бид цаг хугацааны шугаман нарийн төвөгтэй байдалд хүрч чадсан.

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

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