Java 根据因子数量对元素进行排序

在这个问题中，我们的任务是根据数组中存在的数字的多个因子来对整数数组进行排序。数组是在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 ：基于数组中元素的因子数量计算factors[]数组。

步骤4 ：根据factors[]数组作为优先级和数值作为第二优先级对数组[]进行排序。

步骤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：使用分治算法

该算法基于分治技术。在这个算法中，数组[]和计数器[]在分割阶段递归地分割，然后在征服阶段，两个已排序的部分以合并的形式合并。

算法：使用分治算法

第1步 ：输入变量“N”的用户输入。

第2步 ：从用户那里询问“N”个元素，并将它们存储在整数数组“array”中。

第3步 ：根据数组[]中元素的因子数量计算factors[]数组。

第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)

在本文中，我们提供了基于暴力和分治技术的两种方法。其中，分治技术表现良好。