資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告