使用STL对向量进行排序是小菜一碟。我们可以使用著名的sort()函数来完成这个任务。真正的挑战是计算每个数字的因子数量。
因子是能够完全整除另一个数的数字,即余数为零。
遍历所有数字以计算因子可能是一种方法,但我们将在本文中尝试优化和达到高效的解决方案。
根据每个数字的因子数量按升序对给定的数组进行排序。因此,具有最少因子数量的数字应该在开头,具有最多因子数量的数字应该在末尾。具有相同因子数量的数字应按照原始数组的顺序排列。可以使用STL来对数组进行排序。
Input − Array a = [15,2,20,3,10,4] Output − 3 2 4 10 15 20 pre class="just-code notranslate language-cpp" data-lang="cpp"> The number of factors of 15 − 4. The number of factors of 2 − 2. The number of factors of 20 − 6. The number of factors of 3 − 2. The number of factors of 10 − 4. The number of factors of 4 − 3.
因此,根据它们的因子将数字按升序排序后,我们得到输出结果:3 2 4 10 15 20。
Input − Array a = [5,9,12,19,21] Output − 19 5 9 21 12
Explanation
The number of factors of 5 − 3. The number of factors of 9 − 3. The number of factors of 12 − 4. The number of factors of 19 − 2. The number of factors of 21 − 4.因此,在根据它们的因子将数字按升序排序后,我们得到输出:19 5 9 21 12
找出每个数字的因子数量。
创建一个存储数字和其因子计数的一对对的向量。
对向量进行排序并返回结果。
一种天真的方法是遍历从1到n的所有数字,找出它们是否能整除n。这样,我们可以计算每个数字的因子数量。
下面是一个使用蛮力法计算一个数的所有约数的C++程序
#include <bits/stdc++.h> using namespace std; // function to count the divisors int countDivisors(int n){ int count = 0; for (int i = 1; i <= n; i++){ if (n % i == 0) count++; } return count; } int main(){ int n = 55; //Function call int ans = countDivisors(n); cout <<"The number of divisors of 55 is: "<<ans<<endl; return 0; }
The number of divisors of 55 is: 4
一个数的因数存在成对。
例如,12的约数是1、2、3、4、6、12。
但是,我们可以像这样可视化它们:(1,12),(2,6),(3,4)。
因此,如果我们找到一个除数,我们也可以找到另一个除数,而不需要遍历到n。
因此,高效的方法是只遍历到该数的平方根,然后成对计算除数。
下面是一个用于计算一个数的约数的C++程序
#include <bits/stdc++.h> using namespace std; // Function to count the divisors of a number int countDivisors(int n){ int count = 0; for (int i=1; i<=sqrt(n); i++){ if (n%i == 0){ // If divisors are equal, count only one if (n/i == i) count++; else // Otherwise count both count += 2; } } return count; } int main(){ int n = 55; int ans = countDivisors(n); cout <<"The number of divisors of 55 is: "<<ans<<endl; return 0; }
The number of divisors of 55 is: 4
现在,我们可以按照上面讨论的方法的第二步和第三步进行操作。
#include <bits/stdc++.h> using namespace std; // Function to count the divisors of a number int countDivisors(int n){ int count = 0; for (int i=1; i<=sqrt(n); i++){ if (n%i == 0){ // If divisors are equal, count only one if (n/i == i) count++; else // Otherwise count both count += 2; } } return count; } int main(){ int n = 5; vector<int>vec; //Inserting input vec.push_back(5); vec.push_back(14); vec.push_back(18); vec.push_back(9); vec.push_back(10); //Vector of pairs to store the number and its factor count vector<pair<int,int>>count_data(n); for(int i=0;i<n;i++){ //Storing the data in the vector count_data[i] = {countDivisors(vec[i]), vec[i]}; } //Sort the vector according to the number of factors sort(count_data.begin(),count_data.end()); //Printing the result cout<<"The sorted vector based on the number of factors is: n"; for(int i=0;i<n;i++){ cout<<count_data[i].second<<" "; } return 0; }
The sorted vector based on the number of factors is: 5 9 10 14 18
在这篇文章中,我们根据整数的因子数量对一个向量进行了排序。
我们讨论了一些例子,然后谈论了方法。
这个问题的核心是找到一个数的约数的个数。解决这个问题可以有两种方法:蛮力法和高效法。我们看到了这两种方法,然后利用高效法来编写最终的程序。