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:
- 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.
- 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.
- 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))
[3, 3, 3, 5, 2, 2, 1, 1]
Complejidad temporal: O(N*log N).
Complejidad espacial: O(N).