根据因子数量对元素进行排序
javaobject oriented programmingprogramming更新于 2025/1/17 9:48:17
在这个问题中，我们的任务是优先根据数组中存在的几个数字因子对整数数组进行排序。数组是存储 Java 中相似类型元素的最佳方式。但是，如果任何两个数字的因子数量相等，那么作为第二优先级，该算法会查看数值。因子是给定数字可以完全整除而不留下任何余数的数字。本文使用各种方法根据几个因子对元素进行排序。
向您展示一些实例
实例 1
如果数组 = [62, 8, 42, 74, 63]
那么，
Factors(62) = {1, 2, 31, 62} ⇒ 4
Factors(8) = {1, 2, 4, 8} ⇒ 4
Factors(42) = {1, 2, 3, 6, 7, 14, 21, 42} ⇒ 8
Factors(74) = {1, 2, 37, 74} ⇒ 4
Factors(63) = {1, 3, 7, 9, 21, 63} ⇒ 6
排序后的结果数组 = [41, 53, 21, 75, 36]
实例-2
如果数组 = [75, 21, 36, 41, 53]
那么，
Factors(75) = {1, 3, 5, 15, 25, 75} ⇒ 6
Factors(21) = {1, 3, 7, 21} ⇒ 4
Factors(36) = {1, 2, 3, 4, 6, 9, 12, 18, 36} ⇒ 9
Factors(41) = {1, 41} ⇒ 2
Factors(53) = {1, 53} ⇒ 2
排序后的结果数组 = [41, 53, 21, 75, 36]
多种方法
我们提供了不同方法的解决方案。
使用蛮力法。
使用分而治之算法。
让我们按顺序从程序及其输出开始。
方法 1:使用蛮力法
此算法基于蛮力算法。在此排序中，我们对 N 次传递进行成对比较。
算法:使用蛮力法
步骤 1:询问用户想要在变量"N"中输入的元素数量。
步骤 2:向用户询问"N"个元素并将它们存储在整数数组"array"中。
步骤 3:根据 array[] 中元素的因子数量计算 factors[] 数组。
步骤 4:根据 factors[] 数组作为优先级，数值作为第二优先级，对 array[] 进行排序。
步骤 5:在控制台中显示结果。
示例
#include <iostream>
using namespace std;
/**
* Count the number of factors of the number "num"
*
* @num: accepting integer number
* @return count: return the total number of factors
*/
int countFactors(int num) {
int factorsCount = 0;
// traverse i = 1 to num for checking valid factor
for (int fact=1; fact <=num; ++fact) {
// True, if "fact" is a valid factor of "num"
if (num%fact == 0)
++factorsCount;
}
// return the total number of factors of number "num"
return factorsCount;
}
/**
* Swap numbers present in position - pos1 & pos2 in array "arr"
*
* @param array[]
* @param pos1: position of first element in array
* @param pos2: position of second element in array
*/
void swap(int array[], int pos1, int pos2) {
int tempVar = array[pos1];
array[pos1] = array[pos2];
array[pos2] = tempVar;
}
/**
* Sorting array based on number of factors
*
* @param arr[]: array for sorting
* @param n: number of elements present in array "arr"
*/
void sort(int arr[], int n) {
// create counter array for storing the number of factors
// this is used for mapping the number with its factor-counts
int counter[n];
for (int idx=0; idx <n; ++idx)
counter[idx] = countFactors(arr[idx]);
// sort the "array" using the concept of "bubble sort"
for (int pass=0; pass <n; ++pass) {
for (int idx=0; idx <n-pass-1; ++idx) {
// if order is not correct, swap the elements
if ((counter[idx] > counter[idx+1]) || (counter[idx] ==
counter[idx+1] && arr[idx] > arr[idx+1])) {
swap(arr, idx, idx+1);
swap(counter, idx, idx+1);
}
}
}
}
/**
* main() function
*/
int main() {
int N, array[100000];
// ask for the "number" of elements the user wants to enter
cout < < "Enter N: ";
cin >> N;
// ask N elements from the user
cout < < "Enter " < < N < < " Elements: ";
for (int idx=0; idx<N; ++idx) {
cin >> array[idx];
}
// sort the array using function sort()
sort(array, N);
// display the array after sorting
cout < < "Array after Sorting by Factor: ";
for (int idx=0; idx <N; ++idx) {
cout < < array[idx] < < " ";
}
cout < < endl;
// end of program
return 0;
}
输出
Enter N: 5 Enter 5 Elements: 75 21 36 41 53 Array after Sorting by Factor: 41 53 21 75 36
程序的时间复杂度 = O(N*N)
程序的空间复杂度 = O(N)
方法 2:使用分治算法
该算法基于分治技术。在此，array[] 和 counter[] 在除法阶段被递归地划分，然后在征服阶段，两个排序部分以组合排序形式合并。
算法:使用分治算法
步骤 1:获取变量"N"的用户输入。
步骤 2:向用户询问"N"个元素并将它们存储在整数数组"array"中。
步骤 3:计算因数 [] 数组取决于数组[]中元素的因数数量。
步骤 4:递归地将数组分成两半，直到数组的大小保持为 1。
步骤 5:从递归返回后，将数组的两半合并为排序表单。
步骤 6:在控制台中显示排序后的数组。
示例
#include <iostream>
using namespace std;
/**
* count the number of factors of number "num"
*
* @num: accepting integer number
* @return count: return total number of factors
*/
int countFactors(int num) {
int factorsCount = 0;
// traverse i = 1 to num for checking valid factor
for (int fact=1; fact<=num; ++fact) {
// True, if "fact" is a valid factor of "num"
if (num%fact == 0)
++factorsCount;
}
// return the total number of factors of number "num"
return factorsCount;
}
/**
* Merge two sub-arrays, arr[l: m+1] and arr[m+1: r]
* based on counter[] array
*/
void merge(int arr[], int counter[], int l, int m, int r) {
int temp1[r-l+1], temp2[r-l+1];
int i = l, j = m+1, k = 0;
while (i<=m && j<=r) {
if ((counter[i] < counter[j]) || (counter[i] == counter[j]
&& arr[i]<=arr[j])) {
temp1[k] = arr[i];
temp2[k] = counter[i];
i += 1;
}
else {
temp1[k] = arr[j];
temp2[k] = counter[j];
j += 1;
}
k += 1;
}
while (i<=m) {
temp1[k] = arr[i];
temp2[k] = counter[i];
k += 1;
i += 1;
}
while (j<=r) {
temp1[k] = arr[j];
temp2[k] = counter[j];
k += 1;
j += 1;
}
i = 0, j = l;
while (j <= r) {
arr[j] = temp1[i];
counter[j] = temp2[i];
i += 1;
j += 1;
}
}
// recursive algorithm
void sort(int arr[], int counter[], int l, int r) {
if (l >= r)
return;
int m = (l+r)/2;
sort(arr, counter, l, m);
sort(arr, counter, m+1, r);
merge(arr, counter, l, m, r);
}
/**
* main() function
*/
int main() {
int N, array[100000], counter[100000];
// 询问用户想要输入的元素"数量"
cout << "输入 N:";
cin >> N;
// 询问用户 N 个元素
cout << "输入 " << N << " 元素:";
for (int idx=0; idx<N; ++idx) {
cin >> array[idx];
}
// 创建计数器数组以存储因子的数量
// 这用于将数字与其因子计数进行映射
for (int idx=0; idx<N; ++idx)
counter[idx] = countFactors(array[idx]);
// 使用函数 sort() 对数组进行排序
sort(array, counter, 0,N-1);
// 显示排序后的数组
cout << "按因子排序后的数组: ";
for (int idx=0; idx<N; ++idx) {
cout << array[idx] << " ";
}
cout << endl;
// 程序结束
return 0;
}
输出
输入 N:5 输入 5 个元素:62 8 42 74 63 按因子排序后的数组:8 62 74 63 42
程序的时间复杂度 = O(N*log(N))
程序的空间复杂度 = O(N)
在本文中，我们给出了两种基于蛮力和分治技术的方法。其中，分治技术表现良好。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/
