我正在寻找以下问题的解决方案：
Given a array and a number P , find two numbers in array whose product equals P.
寻找比O(n*2)更好的解决方案。 我可以使用额外的空间或其他数据结构。任何帮助都将不胜感激？
给定一个数字 P，在数组中找到两个元素，使它们的乘积等于 P。
6
- TopCoder
4
6这听起来真的像家庭作业。 - Ken Struys
在数字类型方面是否有任何限制（例如只能是整数、只能是正整数等）？ - Michael Aaron Safyan
把以下與編程相關的內容翻譯成中文。只返回已翻譯的文本：沒有數量限制。 - TopCoder
如果没有数字限制（除了可能是实数），存在解的可能性趋近于零，特别是如果其中一个或多个数字是浮点数近似值。经典论文：http://docs.sun.com/source/806-3568/ncg_goldberg.html - msw
11个回答
26
遍历这个数组，并将元素添加到 Hashtable 中。对于每一个添加的元素 x，检查 Hashtable 中是否已经存在 P/x——如果存在，那么 x 和 P/x 就是其中一个解决方案。这是你能得到的最优解了。
- Will A
2
1@Michael - 这有关系吗？虽然P/x可能不是Hashtable中的确切元素，但如果这会造成问题，那么对数组进行排序并进行二进制搜索以定位最接近P/x的元素，并将该元素乘以x以检查P可能是更好的选择。 - Will A
你的答案当然是完全正确的。但是，在实现中必须进行某种程度的量化/分箱才能使其正常工作。不过，对于O(n^2)算法，这样的量化也是必要的。请原谅晚上发布的评论。 :) - Michael Aaron Safyan
12
你可以尝试使用滑动窗口的方法。首先将所有数字按升序排序，然后使用两个整数
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);
}
- jbernadas
5
1我有直觉这可能找不到解决方案。 - pascal
6@pascal：这种技术是可行的，并且可以证明。然而，在排序后执行此操作在复杂度方面并不实用。你可以简单地扫描这些项并使用二分查找来找到互补操作数。总体复杂度仍为O（N Log N）。
这种技术的优点是当数组已经排序时，可以实现线性时间。 - Eyal Schneider
1是的，你说得对。我曾经考虑过将“begin”向前移动一步，以便尝试与更大的“end”配对，但在这个心理想象中，我忽略了数组在“end”一侧也是排序的... - pascal
3这可能不适用于具有负数的数组？例如：v = [-8，-2，2，8]和p = 16。首先，v [begin] * v [end] = -8 * 8 = -64小于16，因此我们继续增加begin。因此，这种方法将错过配对（-8，-2）。 - anil kumar
1@anilkumar：是的。如果P为正数且存在任何负数，则需要在排序后解决2个子问题。设k为第一个包含正数的索引。您需要解决子问题[1..k-1] vs [1..k-1]，可以通过（概念上）反转此范围并“忘记”它们的负号来完成，并且还需要解决子问题[k..n] vs [k..n]（以通常的方式）。如果P为负数，则原始算法的变体起作用：将“begin”从k-1开始，并在当前乘积>P时向后移动。无论哪种方式，它都是O（n）时间，不包括排序时间。 - j_random_hacker
3
这种方法仅适用于整数：
将P分解为质数的乘积。通过将它们分成两组，您可以得到产生P作为乘积的组合。现在你只需要检查它们是否同时出现在数组中，这就是哈希表非常有用的地方。此外，在创建哈希表时，您还可以过滤重复值的数组、大于P的值或具有不包含在P中的质因数的值。
- ruslik
3
好主意，尽管分解可能比O(n²)更复杂一些。 - liori
@liori：不一定，如果你有一个预先计算好的质数列表，那么它的时间复杂度是O(n)。 - ruslik
是的，你说得对。虽然为了分解任何64位整数所需的质数存储需要大约0.8GB的内存。不管怎样，+1。 - liori
1
- 创建哈希表，将在以下步骤中填充。
- 逐一迭代数组元素。假设当前元素为n
- 如果数字P恰好可被n整除
- 检查n是否是哈希表的值之一。如果是，则该键和值就是我们正在寻找的两个数字，我们可以退出循环。
- 如果n不在哈希表的值之一，则将n、x添加到哈希表中，其中n * x = P
- 如果数字P不能被n整除，则继续处理数组的下一个元素
- 如果数字P恰好可被n整除
- 如果我们到达数组末尾，则数组中没有这样的两个数字，其乘积为P
该算法的时间复杂度为O(n)
- chase03
0
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;
}
- NinjaNick
0
已更新以提供实现。
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;
}
}
}
- benCkyCoder
0
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)。
当然，在真实机器上可能会因为浮点误差而遇到困难。
- Bwmat
-1
这是我的尝试，它只会将任何因素彼此比较一次
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++
- Randy the Dev
1
factors 是否曾经被放入任何内容？ - Will A-1
不确定这是否是最佳解决方案，但它可以工作。您可以尝试优化它。
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);
}
- user453695
-1
#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;
}
- Nitesh Prabhat
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接