给定一个数p，发现数组，其产品的两个元素= P [英] given a number p , find two elements in array whose product = P

问题描述

我要寻找的解决方案：

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

寻找比O解决方案更好的（N * 2）。我没关系使用额外的空间或其他数据结构。任何帮助是AP preciated？

Looking for solution better than O(n*2) . I am okay with using extra space or other datastructure .Any help is appreciated ?

推荐答案

您可以尝试滑窗的方法。首先排序所有的数字越来越多，然后用两个整数开始和结束指数目前对数字。初始化开始 0和结束到最后的位置。然后比较 v [开始] 和 v [结束] 与 P ：

You can try a sliding window approach. First sort all the numbers increasingly, and then use two integers begin and end to index the current pair of numbers. Initialize begin to 0 and end to the last position. Then compare the product of v[begin] and v[end] with P:

• 如果是平等的，你找到了答案。
• 如果是较低的，你必须找到一个更大的产品，移动开始前进。
• 如果是更高的，你必须找到一个更小的产品，移动结束落后。

• If it is equal, you found the answer.
• If it is lower, you must find a bigger product, move begin forward.
• If it is higher, you must find a smaller product, move end backward.

下面是一个C ++ code这个想法实现。该解决方案是O，因为排序（N *的log（n）），如果你可以假设数据进行排序，那么你可以跳过一个O排序（N）解决方案。

Here is a C++ code with this idea implemented. This solution is O(n*log(n)) because of the sorting, if you can assume the data is sorted then you can skip the sorting for an O(n) solution.

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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！