我正在寻找以下问题的解决方案:
Given a array and a number P , find two numbers in array whose product equals P.
寻找比O(n*2)更好的解决方案。 我可以使用额外的空间或其他数据结构。任何帮助都将不胜感激?
我正在寻找以下问题的解决方案:
Given a array and a number P , find two numbers in array whose product equals P.
寻找比O(n*2)更好的解决方案。 我可以使用额外的空间或其他数据结构。任何帮助都将不胜感激?
遍历这个数组,并将元素添加到 Hashtable 中。对于每一个添加的元素 x,检查 Hashtable 中是否已经存在 P/x——如果存在,那么 x 和 P/x 就是其中一个解决方案。这是你能得到的最优解了。
begin
和 end
来索引当前的数字对。将begin
初始化为0,将end
初始化为最后一个位置。然后将v [begin]
和v [end]
的乘积与P
进行比较:
begin
向前移动。end
向后移动。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);
}
这种方法仅适用于整数:
将P分解为质数的乘积。通过将它们分成两组,您可以得到产生P作为乘积的组合。现在你只需要检查它们是否同时出现在数组中,这就是哈希表非常有用的地方。此外,在创建哈希表时,您还可以过滤重复值的数组、大于P的值或具有不包含在P中的质因数的值。
该算法的时间复杂度为O(n)
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;
}
已更新以提供实现。
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;
}
}
}
1. 将数字按照O(nlogn)时间进行排序,放入数组A中,移除所有的零。
2. 创建一个数组B,使得B[i] = P/A[I],使用O(n)时间。
3. 对于B中的每个元素B[k],在A中进行二分搜索,最坏情况下需要O(nlogn)时间。
如果元素B[k]在数组A的位置m存在,则有A[k] * A[m] = P;否则,不存在这样的一对元素。
整个运行时间为O(nlogn)。
当然,在真实机器上可能会因为浮点误差而遇到困难。
这是我的尝试,它只会将任何因素彼此比较一次
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++
factors
是否曾经被放入任何内容? - Will A不确定这是否是最佳解决方案,但它可以工作。您可以尝试优化它。
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);
}
#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;
}