数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究基于因子个数排序元素
在这个问题中，我们的任务是根据数组中数字的因子个数（作为优先级）对整数数组进行排序。数组是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：计算factors[]数组，它取决于数组array[]中元素的因子个数。
步骤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];
// ask for "number" of elements user want 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];
}
// create counter array for storing the number of factors
// this is used for mapping the number with its factor-counts
for (int idx=0; idx<N; ++idx)
counter[idx] = countFactors(array[idx]);
// sort the array using function sort()
sort(array, counter, 0,N-1);
// 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 the program
return 0;
}
输出
Enter N: 5 Enter 5 Elements: 62 8 42 74 63 Array after Sorting by Factor: 8 62 74 63 42
程序时间复杂度 = O(N*log(N))
程序空间复杂度 = O(N)
在这篇文章中，我们提供了基于蛮力和分治技术的两种方法。其中，分治技术表现更好。
更新于：2023年8月23日
483 次浏览
广告