по номеру p найти два элемента в массиве, произведение которых = P

Question

Я ищу решение для:

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

Ищет решение лучше, чем O (n * 2). Я в порядке с использованием дополнительного пространства или другой структуры данных. Любая помощь ценится?

Answer 1

Сделайте проход по массиву и добавьте элементы в Hashtable.Для каждого добавленного элемента x проверьте, существует ли P / x в Hashtable - если это так, то x и P / x - одно из ваших решений.Это будет примерно настолько оптимально, насколько вы получите.

Answer 2

Вы можете попробовать подход с раздвижными окнами.Сначала отсортируйте все числа по возрастанию, а затем используйте два целых числа begin и end, чтобы проиндексировать текущую пару чисел.Инициализируйте begin до 0 и end до последней позиции.Затем сравните произведение v[begin] и v[end] с P:

• Если оно равно, вы нашли ответ.
• Если оно ниже, вы должны найтиЧтобы увеличить продукт, двигайтесь на begin вперед.
• Если оно выше, вы должны найти продукт меньшего размера, двигайтесь на end назад.

Вот код C ++ сидея реализована.Это решение O (n * log (n)) из-за сортировки, если вы можете предположить, что данные отсортированы, то вы можете пропустить сортировку для решения 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 3

Это будет работать только для целых чисел: Разложить P как произведение простых чисел. Разделив их на две группы, вы можете получить пары, которые дают P как произведение. Теперь вам просто нужно проверить, что оба они присутствуют в массиве, вот где хеш-таблица была бы очень полезна. Кроме того, при создании хеш-таблицы вы также можете фильтровать массив повторяющихся значений, значений, превышающих P, или даже значений, у которых есть простые множители, не содержащиеся в P.

Answer 4

• Создайте хеш, который будет заполнен в следующих шагах.
• Перебирайте элементы массива один за другим. Скажем, текущий элемент n
  • Если число P точно делится на n
    • проверить, является ли n одним из значений хеша. Если да, тогда этот ключ, значение - это два числа, которые мы ищем, и мы можем их сломать.
    • если n не находится в значениях хеша, то добавить n, x в хеш, где n * x = P
  • Если число P не делится точно на n, переходите к следующему элементу массива
• Если мы достигнем конца массива, то в массиве не будет таких двух чисел, произведение которых равно P

Этот алгоритм имеет O (n)

Answer 5

#include<stdio.h>
int main()
{
 int arr[]={2,15,4,5,6,7};
 const int  c = 30;
 int i = 0,j=1;
 int num =0;
 while ( i<= 6 )
 {
    num = arr[i] * arr[j];
    if ( num == 30)
    {
       printf("Pairs[%d,%d]\t",arr[i],arr[j]);
    }
    if (j == 5 )
    {
       i = i+1;
       j = i + 1;
       if (j==6)
       {
          break;
       }
       else
       {
       continue;
       }
    }
    j= j+1;

 }


 return 0;
}

Answer 6

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;
}

Answer 7

Обновлено для обеспечения реализации.

O (n + P) решения, игнорируя регистр P, равный 0.

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int main(){
    auto arr = new vector<int>();
    int P, numOfEle, ele;

    cout << "The number of elements to be entered: " << endl;
    cin >> numOfEle;
    cout << "Please enter the elements: " << endl;
    for (int i = 0; i < numOfEle; i++){
        cin >> ele;
        arr->push_back(ele);
    }
    cout << "Please enter P: " << endl;
    cin >> P;


    //O(n+P) solution, ignoring the case of P equal to 0
    bool* factorsInNeed = new bool[P];
    for (int i = 0; i < P; i++)
        factorsInNeed[i] = false;
    for (auto i : *arr){
        if (i != 0 && P/(double)i == P/i){ //if divisble
            if (factorsInNeed[i]){
                cout << "A solution: " << i << " & " << P/i << endl;
                break;
            }
            factorsInNeed[P/i] = true;
        }
    }
}

Answer 8

void PrintPairOfProduct (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

Не уверен, что это лучшее решение, но оно работает.Вы можете попробовать и оптимизировать его.

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 10

1.сортировка чисел в массив A, удаление любых нулей за O (nlogn) время

2.создать массив B таким образом, чтобы B [i] = P / A [I] за O (n) раз

3.для каждого B [k] в B выполните бинарный поиск в A для этого элемента, в худшем случае требуется время O (nlogn)

если элемент B [k] существует в массиве A в позиции m, то A [k] * A [m] = P в противном случае такой пары не существует

общее время работы O (nlogn)

Конечно, это может столкнуться с трудностями на реальной машине из-за ошибки с плавающей точкой