Dada una array de enteros, ordene la array de acuerdo con la frecuencia de los elementos en orden decreciente, si la frecuencia de dos elementos es la misma, entonces ordene en orden creciente
Ejemplos:
Input: arr[] = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}
Output: 3 3 3 3 2 2 2 12 12 4 5
Explanation :
No. Freq
2 : 3
3 : 4
4 : 1
5 : 1
12 : 2
Input: arr[] = {4, 4, 2, 2, 2, 2, 3, 3, 1, 1, 6, 7, 5}
Output: 2 2 2 2 1 1 3 3 4 4 5 6 7
Se han discutido diferentes enfoques en las publicaciones a continuación:
Ordenar elementos por frecuencia | Set 1
Ordenar elementos por frecuencia | Set 2
Clasificación de elementos de array por frecuencia | Conjunto 3 (usando STL)
Ordenar elementos por frecuencia | Conjunto 4 (Enfoque eficiente usando hash)
Acercarse:
Java Map se ha utilizado en este conjunto para resolver el problema. La interfaz java.util.Map representa un mapeo entre una clave y un valor. La interfaz Mapa no es un subtipo de la interfaz Colección. Por lo tanto se comporta un poco diferente al resto de tipos de colección.
En el siguiente programa:
- Obtener el elemento con su cuenta en un Mapa
- Mediante el uso de la interfaz Comparator, compare la frecuencia de un elemento en una lista dada.
- Utilice este comparador para ordenar la lista implementando el método Collections.sort() .
- Imprime la lista ordenada.
Programa:
import java.util.*;
public class GFG {
// Driver Code
public static void main(String[] args)
{
// Declare and Initialize an array
int[] array = { 4, 4, 2, 2, 2, 2, 3, 3, 1, 1, 6, 7, 5 };
Map<Integer, Integer> map = new HashMap<>();
List<Integer> outputArray = new ArrayList<>();
// Assign elements and their count in the list and map
for (int current : array) {
int count = map.getOrDefault(current, 0);
map.put(current, count + 1);
outputArray.add(current);
}
// Compare the map by value
SortComparator comp = new SortComparator(map);
// Sort the map using Collections CLass
Collections.sort(outputArray, comp);
// Final Output
for (Integer i : outputArray) {
System.out.print(i + " ");
}
}
}
// Implement Comparator Interface to sort the values
class SortComparator implements Comparator<Integer> {
private final Map<Integer, Integer> freqMap;
// Assign the specified map
SortComparator(Map<Integer, Integer> tFreqMap)
{
this.freqMap = tFreqMap;
}
// Compare the values
@Override
public int compare(Integer k1, Integer k2)
{
// Compare value by frequency
int freqCompare = freqMap.get(k2).compareTo(freqMap.get(k1));
// Compare value if frequency is equal
int valueCompare = k1.compareTo(k2);
// If frequency is equal, then just compare by value, otherwise -
// compare by the frequency.
if (freqCompare == 0)
return valueCompare;
else
return freqCompare;
}
}
2 2 2 2 1 1 3 3 4 4 5 6 7
Complejidad de tiempo: O (n Log n)
Publicación traducida automáticamente
Artículo escrito por bilal-hungund y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA