Policz pary, których produkty istnieją w zestawieniu

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

W parach zliczeniowych, których produkty występują w problemie z tablicami, daliśmy szyk, policz wszystkie różne pary, których wartość iloczynu znajduje się w tablicy.

Przykład

Wkład

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

Wydajność

Liczba różnych par, których iloczyn istnieje w tablicy to: 2

Pary to: (2, 3), (5, 3)

Brute force: Podejście 1 dla zliczania par, których produkt istnieje w tablicy

Powtórz wszystkie pary, a następnie sprawdź, czy ten element istnieje w tablicy, czy nie. Jeśli istnieje, zwiększ odpowiedź o 1.

Algorytm

1. Zainicjuj zmienną ans wartością 0.
2. Uruchom pętlę dla I w zakresie od 0 do n-1;
   1. Uruchom pętlę dla j w zakresie od i + 1 do n-1
      1. Teraz uruchom pętlę dla k w zakresie od 0 do n-1
         1. Jeśli A [i] * A [j] jest równe A [k], to zwiększ ans o 1 i przerwij pętlę.
      2. Drukuj ans.

Program w 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

Program 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

Analiza złożoności dla par, których produkt istnieje w tablicy

Złożoność czasowa: Używamy trzech zagnieżdżonych pętli, wszystkie o rozmiarze N. Więc złożoność czasowa wynosi O (N ^ 3).

Złożoność przestrzeni: Nie używamy żadnej dodatkowej przestrzeni, więc złożoność przestrzeni jest O (1).

Korzystanie z haszowania: podejście 2 dla zliczania par, których produkt istnieje w tablicy

Główny pomysł

Wszystkie elementy tablicy będziemy umieszczać w tablicy haszującej. Następnie dokonamy iteracji po wszystkich parach, jeśli iloczyn par istnieje w tablicy, a następnie zwiększamy odpowiedź o 1. Możemy sprawdzić, czy w tablicy występuje iloczyn, czy nie, wyszukując w tablicy haszującej w stałym czasie.

Algorytm

1. Zadeklaruj tablicę skrótów.
2. Zainicjuj zmienną ans wartością 0, która zapisze odpowiedź.
3. Uruchom pętlę dla I w zakresie od 0 do n-1.
   1. Uruchom pętlę dla j w zakresie od j + 1 do n-1;
      1. Jeśli iloczyn A [i] i A [j] jest obecny w tablicy haszującej, należy zwiększyć ans o 1.
   2. Drukuj ans.

Na przykład:

Dla tablicy A [] = {2, 4, 2, 4, 15, 8, 20}

Tabela skrótów będzie wyglądać następująco:

szpilka

Program w 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

Program 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

Analiza złożoności dla par, których produkt istnieje w tablicy

Złożoność czasowa: Używamy dwóch zagnieżdżonych pętli, obie o rozmiarze N. Więc złożoność czasowa wynosi O (N ^ 2).

Złożoność przestrzeni: Utrzymujemy tablicę mieszającą do przechowywania elementów tablicy. Tak więc jest złożoność przestrzeni NA).

Referencje