给定一个数字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,检查H /中是否已存在P/x - 如果是,则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);
}