数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 中的最近公约数
假设我们有一个整数 num，我们必须找到绝对差中最近的两个整数，它们的乘积等于 num + 1 或 num + 2。我们必须以任何顺序找到这两个整数。因此，如果输入为 8，那么输出将为 [3, 3]，对于 num + 1，它将为 9，最近的公约数为 3 和 3，对于 num + 2 = 10，最近的公约数为 2 和 5，因此选择 3 和 3。
为了解决这个问题，我们将遵循以下步骤：
定义一个名为 getDiv() 的方法，它将 x 作为输入
diff := 无穷大，创建一个名为 ret 的大小为 2 的数组
对于 i := 1，如果 i^2 <= x，则将 i 增加 1
如果 x 可以被 i 整除，则
a := i
b := x / i
newDiff := |a – b|
如果 newDiff < diff，则
diff := newDiff
ret[0] := a 且 ret[1] := b
返回 ret
从 main 方法中，找到 op1 := getDiv(num + 1) 且 op2 := getDiv(num + 2)
如果 |op1[0] – op[1]| <= |op2[0] – op2[1]|，则返回 op1，否则返回 op2
示例 (C++)
让我们看看以下实现以获得更好的理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector <int> getDiv(int x){
int diff = INT_MAX;
vector <int> ret(2);
for(int i = 1; i * i <= x; i++){
if(x % i == 0){
int a = i;
int b = x / i;
int newDiff = abs(a - b);
if(newDiff < diff){
diff = newDiff;
ret[0] = a;
ret[1] = b;
}
}
}
return ret;
}
vector<int> closestDivisors(int num) {
vector <int> op1 = getDiv(num + 1);
vector <int> op2 = getDiv(num + 2);
return abs(op1[0] - op1[1]) <= abs(op2[0] - op2[1]) ? op1 : op2;
}
};
main(){
Solution ob;
print_vector(ob.closestDivisors(8));
}输入
8
输出
[3,3]
更新于：2020 年 4 月 29 日
325 次浏览
广告