Ordenar elementos según el número de factores

Dada una array de enteros positivos. Ordene la array dada en orden decreciente del número de factores de cada elemento, es decir, el elemento que tiene el mayor número de factores debe ser el primero en mostrarse y el número que tiene el menor número de factores debe ser el último. Dos elementos con el mismo número de factores deben estar en el mismo orden que en la array original.
Ejemplos: 
 

Input : {5, 11, 10, 20, 9, 16, 23}
Output : 20 16 10 9 5 11 23
Number of distinct factors:
For 20 = 6, 16 = 5, 10 = 4, 9 = 3
and for 5, 11, 23 = 2 (same number of factors
therefore sorted in increasing order of index)

Input : {104, 210, 315, 166, 441, 180}
Output : 180 210 315 441 104 166

Los siguientes pasos ordenan los números en orden decreciente de conteo de factores. 
 

  1. Cuente un número distinto de factores de cada elemento. Consulte esto .
  2. Puede usar una estructura para cada elemento para almacenar su índice original y el recuento de factores. Cree una array de tales estructuras para almacenar dicha información para todos los elementos.
  3. Ordene esta array de estructuras sobre la base de la declaración del problema utilizando cualquier algoritmo de clasificación.
  4. Recorra esta array de estructuras desde el principio y obtenga el número de la array original con la ayuda del índice almacenado en la estructura de cada elemento de la array ordenada de estructuras.

C++

// C++ implementation to sort numbers on
// the basis of factors
#include <bits/stdc++.h>
 
using namespace std;
 
// structure of each element having its index
// in the input array and number of factors
struct element
{
    int index, no_of_fact;
};
 
// function to count factors for
// a given number n
int countFactors(int n)
{
    int count = 0;
    int sq = sqrt(n);
     
    // if the number is a perfect square
    if (sq * sq == n)
        count++;
     
    // count all other factors
    for (int i=1; i<sqrt(n); i++)
    {
        // if i is a factor then n/i will be
        // another factor. So increment by 2
        if (n % i == 0)   
            count += 2;
    }       
     
    return count;
}
 
// comparison function for the elements
// of the structure
bool compare(struct element e1, struct element e2)
{
    // if two elements have the same number
    // of factors then sort them in increasing
    // order of their index in the input array
    if (e1.no_of_fact == e2.no_of_fact)
        return e1.index < e2.index;
     
    // sort in decreasing order of number of factors
    return e1.no_of_fact > e2.no_of_fact;   
}
 
// function to print numbers after sorting them in
// decreasing order of number of factors
void printOnBasisOfFactors(int arr[], int n)
{   
    struct element num[n];
     
    // for each element of input array create a
    // structure element to store its index and
    // factors count
    for (int i=0; i<n; i++)
    {
        num[i].index = i;
        num[i].no_of_fact = countFactors(arr[i]);       
    }
     
    // sort the array of structures as defined
    sort(num, num+n, compare);
     
    // access index from the structure element and corresponding
    // to that index access the element from arr
    for (int i=0; i<n; i++)
        cout << arr[num[i].index] << " ";
}
 
// Driver program to test above
int main()
{
    int arr[] = {5, 11, 10, 20, 9, 16, 23};
    int n = sizeof(arr) / sizeof(arr[0]);
    printOnBasisOfFactors(arr, n);
    return 0;
}

Java

// Java implementation to sort numbers on
// the basis of factors
 
import java.util.Arrays;
import java.util.Comparator;
 
class Element
{
    //each element having its index
    // in the input array and number of factors
    int index, no_of_fact;
  
    public Element(int i, int countFactors)
    {
        index = i;
        no_of_fact = countFactors;
    }
 
    // method to count factors for
    // a given number n
    static int countFactors(int n)
    {
        int count = 0;
        int sq = (int)Math.sqrt(n);
      
        // if the number is a perfect square
        if (sq * sq == n)
            count++;
      
        // count all other factors
        for (int i=1; i<Math.sqrt(n); i++)
        {
            // if i is a factor then n/i will be
            // another factor. So increment by 2
            if (n % i == 0)   
                count += 2;
        }       
      
        return count;
    }
  
    // function to print numbers after sorting them in
    // decreasing order of number of factors
    static void printOnBasisOfFactors(int arr[], int n)
    {   
        Element num[] = new Element[n];
      
        // for each element of input array create a
        // structure element to store its index and
        // factors count
        for (int i=0; i<n; i++)
        {
            num[i] = new Element(i,countFactors(arr[i]));
        }
      
        // sort the array of structures as defined
        Arrays.sort(num,new Comparator<Element>() {
 
            @Override
            // compare method for the elements
            // of the structure
            public int compare(Element e1, Element e2) {
                // if two elements have the same number
                // of factors then sort them in increasing
                // order of their index in the input array
                if (e1.no_of_fact == e2.no_of_fact)
                 return e1.index < e2.index ? -1 : 1;
               
                // sort in decreasing order of number of factors
                return e1.no_of_fact > e2.no_of_fact ? -1 : 1; 
            }
             
        });
      
        // access index from the structure element and corresponding
        // to that index access the element from arr
        for (int i=0; i<n; i++)
            System.out.print(arr[num[i].index]+" ");
    }
  
    // Driver program to test above
    public static void main(String[] args)
    {
         
        int arr[] = {5, 11, 10, 20, 9, 16, 23};
         
        printOnBasisOfFactors(arr, arr.length);
 
    }
}
// This code is contributed by Gaurav Miglani

Javascript

<script>
// Javascript implementation to sort numbers on
// the basis of factors
 
// each element having its index
// in the input array and number of factors
class Element {
  constructor(i, countFactors) {
    this.index = i;
    this.no_of_fact = countFactors;
  }
}
 
// method to count factors for
// a given number n
function countFactors(n) {
  let count = 0;
  let sq = Math.floor(Math.sqrt(n));
 
  // if the number is a perfect square
  if (sq * sq == n)
    count++;
 
  // count all other factors
  for (let i = 1; i < Math.sqrt(n); i++) {
    // if i is a factor then n/i will be
    // another factor. So increment by 2
    if (n % i == 0)
      count += 2;
  }
 
  return count;
}
 
// function to print numbers after sorting them in
// decreasing order of number of factors
function printOnBasisOfFactors(arr, n) {
  let num = new Array(n);
 
  // for each element of input array create a
  // structure element to store its index and
  // factors count
  for (let i = 0; i < n; i++) {
    num[i] = new Element(i, countFactors(arr[i]));
  }
 
  // sort the array of structures as defined
 
  num.sort((e1, e2) => {
    // if two elements have the same number
    // of factors then sort them in increasing
    // order of their index in the input array
    if (e1.no_of_fact == e2.no_of_fact)
      return e1.index < e2.index ? -1 : 1;
 
    // sort in decreasing order of number of factors
    return e1.no_of_fact > e2.no_of_fact ? -1 : 1;
  })
 
 
 
 
 
  // access index from the structure element and corresponding
  // to that index access the element from arr
  for (let i = 0; i < n; i++)
    document.write(arr[num[i].index] + " ");
}
 
// Driver program to test above
let arr = [5, 11, 10, 20, 9, 16, 23];
printOnBasisOfFactors(arr, arr.length);
 
// This code is contributed by gfgking
</script>

Producción: 
 

20 16 10 9 5 11 23

Complejidad de tiempo: O(n √n)
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *