时间戳

首页 > 解决方案 > 找到两对数字，使它们的乘积绝对差最小化

c++ - 找到两对数字，使它们的乘积绝对差最小化

问题描述

问题：

给定一个整数 num，找出其乘积等于 num + 1 或 num + 2 的绝对差中最接近的两个整数。

以任意顺序返回两个整数。

我试过这个：

vector<int> closestDivisors(int num) {
    
    if(num == 1)
        return {1,2};
    int first = num + 1, second = num + 2;
    std::vector<int> result(2);        
    auto vec1 = properDivisors(first);
    auto vec2 = properDivisors(second);
    std::map<int, std::pair<int,int>> m;
    int min_k1 = INT_MAX;
    for(auto it1 : vec1)
    {
        for(auto it2 : vec1)
        {
            if (it1 * it2 == first)
            {
                min_k1 = abs(it1-it2);
                m[min_k1] = {it1, it2};
            }
        }
    }
    
    int min_k2 = INT_MAX;
    for(auto it1 : vec2)
    {
        for(auto it2 : vec2)
        {
            if (it1 * it2 == second)
            {
                min_k2 = abs(it1-it2);
                m[min_k2] = {it1, it2};
            }
        }
    }

    for(auto it : m)
    {
        result[0] = it.second.first;
        result[1] = it.second.second;
        if(result.size() == 2)
            break;
    }
    
    
    

    return result;
}


std::vector<long long> properDivisors(int number) {
   std::vector<long long> divisors ;
   for ( int i = 1 ; i < number / 2 + 1 ; i++ )
      if ( number % i == 0 )
     divisors.push_back( i ) ;
   return divisors ;
}

但我不断收到超过时间限制。有没有更有效的方法来实现这一目标？

标签： c++algorithm

解决方案

使用向量可能会使它比需要的慢得多。我将按如下方式处理它。

设置lo为1和。hi_ num + 1这是获取两个整数的起点，这些整数乘以所需的值之一（然后更接近1，num + 2因此您可以忽略这种可能性）。

然后简单地移动lo并hi朝向彼此（直到它们交叉）检查产品以查看它是否等于所需值。这两个数字正在接近这一事实意味着，任何后来的成功都将使它们比之前的数字更接近。

唯一棘手的一点是数字如何相互接近，但这比您想象的要简单。如果乘积小于num + 1，则减少hi将意味着它离期望值更远lo，因此在这种情况下您需要增加。

另一方面，乘积大于num + 2意味着你应该减少hi（增加lo会使乘积更高，因此离期望值更远）。

如果它等于num + 1或num + 2，您可以选择任一选项。之所以没有关系，是因为 and 之间的绝对差异lo + 1与and (a)hi之间的绝对差异相同。lohi -1

例如，这是一个 Python 程序，它显示了它的实际效果：

num = int(input("Number: "))
lo = 1
hi = num + 1
found = None
while lo <= hi: # Make this '<' if numbers must be different.
    prod = lo * hi
    if prod == num + 1 or prod == num + 2:
        found = (lo, hi)
        mark = ' *'
    else:
        mark = ""
    print(f"Low = {lo}, high = {hi}, product = {prod}{mark}")
    if prod < num + 1:
        lo += 1
    else:
        hi -= 1
print(found)

随着几个运行：

Number: 3
Low = 1, high = 4, product = 4 *
Low = 1, high = 3, product = 3
Low = 2, high = 3, product = 6
Low = 2, high = 2, product = 4 *
(2, 2)

Number: 10
Low = 1, high = 11, product = 11 *
Low = 1, high = 10, product = 10
Low = 2, high = 10, product = 20
Low = 2, high = 9, product = 18
Low = 2, high = 8, product = 16
Low = 2, high = 7, product = 14
Low = 2, high = 6, product = 12 *
Low = 2, high = 5, product = 10
Low = 3, high = 5, product = 15
Low = 3, high = 4, product = 12 *
Low = 3, high = 3, product = 9
(3, 4)

Number: 100
Low = 1, high = 101, product = 101 *
Low = 1, high = 100, product = 100
Low = 2, high = 100, product = 200
Low = 2, high = 99, product = 198
: : : (lots of stuff irrelevant to final result)
Low = 6, high = 18, product = 108
Low = 6, high = 17, product = 102 *
Low = 6, high = 16, product = 96
Low = 7, high = 16, product = 112
Low = 7, high = 15, product = 105
Low = 7, high = 14, product = 98
Low = 8, high = 14, product = 112
Low = 8, high = 13, product = 104
Low = 8, high = 12, product = 96
Low = 9, high = 12, product = 108
Low = 9, high = 11, product = 99
Low = 10, high = 11, product = 110
Low = 10, high = 10, product = 100
(6, 17)

正如评论中所指出的，这只处理积极的输入。您也可以通过更改来满足负面输入：

lo = 1
hi = num + 1

至：

lo = -num - 1
hi = num + 1
if lo > hi:
    (lo, hi) = (hi, lo)

这包含了解决方案的积极和消极领域，增加了一点额外的时间，但仍然相当快。

(a)我对我的数学只有 99.99% 的把握，所以，如果有人能提供一个反例，我会很乐意编辑答案（或者甚至删除它，如果我无法修复它，尽管有任何问题可能会在边缘情况下找到存在，因此可能会通过一些简单的预检查来修复）。让我知道。

推荐阅读