Ordenar una array en orden descendente según la suma de sus ocurrencias

Dada una array no ordenada de enteros que pueden contener elementos repetidos, ordene los elementos en orden descendente de algunas de sus ocurrencias. Si existe más de un elemento cuya suma de ocurrencias es la misma entonces, el que sea mayor irá primero. 
Ejemplos: 
 

Entrada: arr[] = [2, 4, 1, 2, 4, 2, 10] 
Salida: arr[] = [10, 4, 4, 2, 2, 2, 1]
Explicación: 
Aquí, 2 aparece 3 veces , 4 aparece 2 veces, 1 aparece 1 vez y 10 aparece 1 vez. 
Por lo tanto, 
Suma de todas las apariciones de 2 en una array dada = 2 * 3 = 6, 
Suma de todas las apariciones de 4 = 4 * 2 = 8, 
Suma de todas las apariciones de 10 = 10 * 1 = 10, 
Suma de todas las apariciones de 1 = 1 * 1 = 1. 
Por lo tanto, ordenar la array en orden descendente según la suma anterior = [ 10, 4, 4, 2, 2, 2, 1 ]
Input2: arr[] = [2, 3, 2, 3, 2, 1, 1, 9, 6, 9, 1, 2] 
Salida 2: [9, 9, 2, 2, 2, 2, 6, 3, 3, 1, 1, 1] 
 

Acercarse: 
 

  1. Cree un mapa que asignará elementos a su apariencia, es decir, si a ocurre una vez, a se asignará a a, pero si a ocurre m veces, a se asignará a a*m.
  2. Después de hacer el mapeo, ordene el diccionario en orden descendente según sus valores, no las claves. En caso de empate, ordenar en base a valores.
  3. Finalmente, copie las claves del diccionario ordenadas en la array de salida final y se obtiene la frecuencia en función de sus pares clave-valor, es decir, si a se asigna a a*m, significa que debemos incluir a, m veces en la array de salida.

A continuación se muestra la implementación del enfoque anterior:
 

Python

# Python3 program to sort elements of
# arr[] in descending order of sum
# of its occurrence
  
def sort_desc(arr):
     
    # to store sum of all
    # occurrences of an elements
    d_sum = {}
 
    # to store count of
    # occurrence of elements
    d_count ={}
 
    # to store final result
    ans = []
 
    # to store maximum sum of occurrence
    mx = 0
      
    # Traverse and calculate sum
    # of occurrence and count of
    # occurrence of elements of arr[]
    for x in arr:
        if x not in d_sum:
            d_sum[x] = x
            d_count[x] = 1
        else:
            d_sum[x] += x
            d_count[x] += 1
             
    # sort d_sum in decreasing order of its value
    l = sorted(d_sum.items(), 
               reverse = True,
               key = lambda x:(x[1], x[0]))
 
    # store the final result
    for x in l:
        ans += [x[0]] * d_count[x[0]]
         
    return ans
      
# Driver Code
arr = [3, 5, 2, 2, 3, 1, 3, 1]
print(sort_desc(arr))
Producción: 

[3, 3, 3, 5, 2, 2, 1, 1]

 

Complejidad temporal: O(N*log N). 
Complejidad espacial: O(N).
 

Publicación traducida automáticamente

Artículo escrito por AshmitRaj 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 *