数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找自然数 N 的第 k 小的除数
在这个问题中，我们给定两个整数值 N 和 k。我们的任务是查找自然数 N 的第 k 小的除数。
让我们举个例子来理解这个问题，
Input : N = 15, k = 3 Output : 5
解释 -
Factors of 15 are 1, 3, 5, 15 3rd smallest is 5
解决方案方法
解决此问题的一个简单方法是找到数字的因子并以排序的方式存储它们，然后打印第 k 个值。
对于排序，我们将循环到根号(N) 并检查 N 是否可被 i 整除。并将 i 和 (N/i) 的值存储在一个数组中并对其进行排序。从这个排序后的数组中，打印第 k 个值。
示例
程序说明我们解决方案的工作原理
#include <bits/stdc++.h>
using namespace std;
void findFactorK(int n, int k){
int factors[n/2];
int j = 0;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
factors[j] = i;
j++;
if (i != sqrt(n)){
factors[j] = n/i;
j++;
}
}
}
sort(factors, factors + j);
if (k > j)
cout<<"Doesn't Exist";
else
cout<<factors[k-1];
}
int main(){
int N = 16,
k = 3;
cout<<k<<"-th smallest divisor of the number "<<N<<" is ";
findFactorK(N, k);
return 0;
}输出
3-th smallest divisor of the number 16 is 4
另一种方法
解决此问题的另一种方法是使用两个排序的数组。
一个存储值 i，按升序排序。
另一个存储值 N/i，按降序排序。
我们将从这两个数组中的任何一个找到第 k 小的值。如果 k 大于数组的大小，则它存在于第二个数组的末尾。
否则它存在于第一个数组中。
示例
程序说明我们解决方案的工作原理
#include <bits/stdc++.h>
using namespace std;
void findFactorK(int n, int k){
int factors1[n/2];
int factors2[n/2];
int f1 = 0,f2 = 0;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
factors1[f1] = i;
f1++;
if (i != sqrt(n)){
factors2[f2] = n/i;
f2++;
}
}
}
if (k > (f1 + f2))
cout<<"Doesn't Exist";
else{
if(k <= f1)
cout<<factors1[f1-1];
else
cout<<factors2[k - f2 - 1];
}
}
int main(){
int N = 16,
k = 3;
cout<<k<<"-th smallest divisor of the number "<<N<<" is ";
findFactorK(N, k);
return 0;
}输出
3-th smallest divisor of the number 16 is 4
更新于: 2022-01-28
409 次查看
广告