donné un nombre p, trouver deux éléments dans le tableau dont le produit = P

Question

Je cherche une solution pour:

Given a array and a number P , find two numbers in array whose product equals P. 

Vous recherchez une solution mieux que O (n * 2). Je suis d'accord avec l'utilisation de l'espace supplémentaire ou autre infrastructure de données. Toute aide est appréciée?

Answer 1

Vous pouvez essayer une approche de fenêtre coulissante. Commencez par trier tous les nombres de plus en plus, puis utilisez deux entiers begin et end pour indexer la paire de nombres actuelle. Initialisez begin à 0 et end à la dernière position. Ensuite, comparez le produit de v[begin] et v[end] avec P:

• Si elle est égale, vous avez trouvé la réponse.
• Si elle est inférieure, vous devez trouver un plus gros produit, déplacez begin vers l'avant.
• S'il est plus élevé, vous devez trouver un produit plus petit, déplacez end vers l'arrière.

Voici un code C++ avec cette idée implémentée. Cette solution est O (n * log (n)) à cause du tri, si vous pouvez supposer que les données sont triées, vous pouvez ignorer le tri pour une solution O (n).

pair<int, int> GetProductPair(vector<int>& v, int P) { 
    sort(v.begin(), v.end()); 
    int begin = 0, end = static_cast<int>(v.size()) - 1; 
    while (begin < end) { 
    const int prod = v[begin] * v[end]; 
    if (prod == P) return make_pair(begin, end); 
    if (prod < P) ++begin; 
    else --end; 
    } 
    return make_pair(-1, -1); 
} 

Answer 2

Effectuez un passage dans le tableau et ajoutez les éléments à une table de hachage. Pour chaque élément x ajouté, vérifiez si P/x existe déjà dans la table de hachage - si c'est le cas alors x et P/x sont l'une de vos solutions. Ce serait à peu près aussi optimal que vous obtiendrez.

Answer 3

Voilà mon coup, il ne compare que des facteurs entre eux une fois

P <- The Number 
theArray <- new array[theData] 
factors <- new array[] 
isFactor <- new map(init: false) 
factorCount <- 0 
i <- 0 
while i is in theArray 
    num <- theArray[i] 
    if (isFactor[num]) 
     skip 
    if num modulo P == 0 
     isFactor[num] <- true 
     j <- 0 
     while j is in factors 
      if factors[j] * num == P 
       return (num, factors[j]) 
      j++ 
     factors.push(num) 
     factorCount++ 
    i++ 

Answer 4

Celui-ci ne peut fonctionner que pour les entiers: Décomposer P en tant que produit de nombres premiers. En les divisant en deux groupes, vous pouvez obtenir les paires qui donnent P comme produit. Maintenant vous avez juste à vérifier les deux sont présents dans le tableau, c'est là qu'une table de hachage serait très utile. En outre, lors de la création de la table de hachage, vous pouvez également filtrer le tableau de valeurs répétées, les valeurs supérieures à P ou même les valeurs ayant des facteurs premiers non contenus dans P.

Answer 5

1.sort les nombres dans un tableau A , en supprimant les zéros, en O (n log n) fois

2.Créez une matrice B telle que B [i] = P/A [I] en O (n)

3.Aux chaque B [ k] dans B, faire une recherche binaire dans A pour cet élément, prend le temps O (nlogn) dans le pire des cas

si l'élément B [k] existe dans le tableau A à la position m, alors A [k] * A [m] = P sinon pas une telle paire existe

le temps total de fonctionnement est O (nlogn)

Bien sûr, cela peut rencontrer des difficultés sur une machine réelle en raison d'une erreur de virgule flottante

Answer 6

Je ne sais pas si c'est le meilleur solution mais cela fonctionne. vous pouvez essayer de l'optimiser.

public class CombInput 
    { 
     public int ID; 
     public string Value; 
    } 

    public List<string> GetCombinations(List<string> values) 
     { 

      List<CombInput> input = new List<CombInput>(); 
      List<string> outputvalues = new List<string>(); 
      int counter = 1; 
      foreach (String c in values) 
      { 
       input.Add(new CombInput { ID = counter, Value = c }); 

       counter++; 
      } 
      var Output = from i in input 
         select i; 

      string Final = Output.Select(query => query.Value).Aggregate((a, b) => a + "|" + b); 

      while (!Output.ToList().Exists(s=>s.Value.ToString()==Final)) 
      { 
       var store = Output; 
       var Output1= 
       (from o in Output 
          from v in input 
         where (v.ID < o.ID && !(store.Any(a=>a.Value==v.Value + "|" + o.Value))) 
           select new CombInput { ID = v.ID, Value = v.Value + "|" + o.Value }); 

       var Outputx = (from s in store select s) 
       .Concat 
       (from s in Output1.ToList() select s); 
       Output = Outputx; 
      } 


      foreach (var v in Output) 
       outputvalues.Add(v.Value); 
      return outputvalues.ToList(); 
     } 

public List<string> GetProductCombinations(List<int> nums, int productCriteria) 
     { 
      List<string> input = (from i in nums 
           select i.ToString()).ToList(); 
      input = GetCombinations(input); 

      var O = from i in input 
        where i.Split('|').ToList().Select(x => Convert.ToInt32(x)).ToList().Aggregate((a, b) => a * b) == productCriteria 
        select i; 


      List<string> output=new List<string>(); 
      foreach (string o in O) 
      { 
       output.Add(o); 
      } 
      return output; 
     } 


private void button1_Click(object sender, EventArgs e) 
     { 

      List<string> output = new List<string>(); 
      List<int> nums = new List<int>(); 
      int[] numsarr ={1,2,3,4,6,7,8,12}; 
      nums = numsarr.ToList(); 
      output = GetProductCombinations(nums, 12); 
} 

Answer 7

• Créer une table de hachage qui sera rempli dans les étapes ci-dessous.
• Effectuez une itération sur les éléments de la matrice un par un. Dire élément courant est n
  • Si le nombre P est divisible par n
    • vérifier si n est l'une des valeurs de hachage. Si oui alors cette clé, la valeur sont les deux nombres que nous cherchons et nous pouvons casser.
    • si n est pas dans les valeurs du hachage puis ajouter n, x dans un hachage n * x = P
  • Si le nombre P est pas exactement divisible par n puis continuer avec l'élément suivant du tableau
• Si nous arrivons à la fin du tableau, alors il n'y a pas ces deux chiffres dans le tableau dont le produit est P

Cette algo est de O (n)

Answer 8

vide Imprimer PairOfProduct (int arr [], int size, int k) {

  int i,temp[MAX]; 
      memset(temp,1,MAX); 
      for(i=0;i<size;++i) 
      { 
      if(k % arr[i] == 0 && temp[arr[i]] != -1 && temp[k/arr[i]] != -1) 
      { 
      if((temp[k/arr[i]] * arr[i]) == k) 
      { 
      printf("Product of %d * %d = %d",k/arr[i],arr[i],k);`` 

      temp[k/arr[i]] = -1; 
      temp[arr[i]] = -1; 
      } 
      temp[arr[i]] = arr[i]; 

}}

Answer 9

Ci-dessous peut être l'une des solutions. Je suis juste un débutant. S'il vous plaît pardonnez-moi s'il y a un problème dans mon algorithme.

Supposons que le tableau d'entrée soit inputArr et supposons que la plage de valeurs des éléments de inputArr est >= 0, <= M.

Créez un tableau booléen, à savoir presenceOfInputValue, de taille, M + 1, et tous ses éléments sont initialisés pour être faux. Une fois qu'une valeur x est trouvée présente dans inputArr, presenceOfInputValue[x] = true.

Cela signifie que si presenceOfInputValue[x] == true, x est présent dans le tableau d'entrée.

Let double Bi = p/arr[i]. 

boucle pour obtenir tous les Bi et mis en place la presenceOfInputValue, et si Bi est un entier, vérifiez si elle est présente dans inputArr en vérifiant si presenceOfInputValue[i] == true.

P.S. Supposons M = 256^4(4bytes) - 1, presenceOfInputValue occupera 256^4/8/1000/1000 ~= 16.8MB

Answer 10

public boolean factors_Of_Product_In_Array(int a[],int product,int factorsLimit) 
{ 
    int i = 0,count = 0; 
    boolean flag = false; 

    if(factorsLimit==0) 
     flag = false; 

    //If product value is zero - only verify if there is any '0' value in array 
    else if(product==0) 
    { 
     for(i=0;i<a.length;i++) 
     { 
      if(a[i]==0) 
       flag = true; 
     } 
    } 

    //If product value is 1 - Verify at least factorsLimit number of 1's should be present in array 
    else if(product==1) 
    { 
     for(i=0;i<a.length;i++) 
     { 
      if(a[i]==0) 
       count=count+1; 
     } 

     if(count==factorsLimit)//Verifying if the number of 1's is equal to number of factors required 
      flag = true; 
    } 

    else 
    { 
     for(i=0; i<a.length && count!=factorsLimit ;i++) 
     { 
      if(product%a[i]==0) 
      { 
       product = product/a[i]; 
       count = count+1; 
       System.out.println(" "+a[i]+" "); 
      } 
     } 

    if(count==factorsLimit) 
     flag = true; 
    } 

    return flag; 
}