Quel est le moyen le plus efficace de trier les éléments d'un tableau en fonction de la fréquence des éléments

Vous pouvez créer une liste à partir du entrySet de la carte, puis trier la liste à l'aide d'un comparateur personnalisé qui compare en fonction des valeurs de la carte.

1. Création d'une liste à partir du entrySet de la carte - utilisez le constructeur qui prend une autre collection comme argument.
2. Tri de la liste - Collections.sort à l'aide d'une implémentation de Comparator.

À partir de Java-8:

  int [] array = {2,2,4,5,7,6,4,8,3,9,5,7,2};
  Map<Integer, Integer> collect = Arrays.stream(array).boxed()
      .collect(Collectors.groupingBy(Function.identity(), Collectors.reducing(0, e -> 1, Integer::sum)));
  System.out.println(collect);

Attention, si vous utilisez Collectors.counting () , vous obtiendrez alors Map , mais selon votre solution, il semble que vous souhaitiez Map , utilisez donc Collectors.reducing (0, e -> 1, Integer :: sum )

Avec une charge mémoire supplémentaire largement inférieure à celle de votre exemple (seulement 200% supplémentaire, dans le pire des cas), et une caractéristique de performance de O (n log n); Je suis presque sûr que vous ne pouvez pas le battre de manière algorithmique, bien qu'avec beaucoup de travail supplémentaire, vous puissiez réduire la charge de la mémoire au pire des cas 100% supplémentaire; ça ne vaut probablement pas la peine.

L'algorithme, en un mot:

Créez un nouveau tableau de longs. Chaque long est bitpacked; il contient 2 informations distinctes: les 32 bits inférieurs correspondent au nombre normal (cela correspond, car les entiers sont 32 bits); les 32 bits supérieurs sont utilisés pour stocker la fréquence (à quelle fréquence le nombre apparaît dans l'entrée).

Afin de créer efficacement votre nouveau tableau long, commencez par trier votre tableau d'entrée; cela prend O (n log n), et signifie que vous pouvez ensuite parcourir une fois votre tableau d'entrée pour créer votre long tableau. Ensuite, triez celui-ci, qui mettra l'élément le plus fréquent à l'arrière. Inversez-le si besoin, si vous voulez le plus fréquent à l'avant. (les nombres de paquets de bits de fréquence plus élevée sont plus grands, car ses 32 bits supérieurs sont les plus élevés); c'est une autre opération O (n log n). Donc, c'est 2 O (n log n) opérations et une seule O (n) op, pour un grand total de O (n log n).

Quelques informations pertinentes sur l'API et Java:

• Tri des tableaux int et long: java.util.Arrays.sort (int [] ou long [])

• bitpacking: vous avez besoin de l'opérateur | et de l'opérateur << . Pour bitpack 2 entiers dans un long, par exemple:

  int count = 5; // représente la fréquence d'affichage de 'nombre'. nombre int = 85; long emballé = (((long) count) << 32) | nombre;

• bit unpacking: pour transformer un long emballé en composants:

  emballé longtemps = ....; // à partir du calcul ci-dessus nombre int = (int) (compacté >> 32); // sera 5 nombre int = (int) emballé; // aura 85 ans

Vous devez faire un jeu de jambes sophistiqué pour gérer le long [] tableau contenant les informations compactées; après tout, ce tableau a probablement moins d'éléments (étant donné une entrée [1,2,5,1,2], votre long tableau compressé a 3 entrées: Le résultat compacté de [{count = 2, number = 1}, {count = 2, number = 2} et {count = 1, number = 5}], donc seulement 3 entrées; soit passez d'abord par votre tableau d'entrées trié une fois pour déterminer sa taille, puis refaites-le pour le remplir , ou faites en sorte que le long tableau soit aussi grand que votre tableau d'entrée (ce qui correspond à sa taille dans le pire des cas, c'est-à-dire lorsque tous les nombres du tableau d'entrée sont uniques), et écrivez du code pour savoir qu'un 0 dans votre le long tableau doit être ignoré.

Pour remplir le long tableau, parcourez simplement votre tableau d'entrée trié. Cela ressemblera à [1,1,2,2,5] que vous devez convertir en [emballé (2,1), emballé (2,2), emballé (1,5)]. Je vais laisser cela comme un exercice pour vous.

Je ne sais pas à propos de short, mais vous pouvez implémenter un simple queue de priorité qui rend votre code plus lisible. La complexité en temps est O (n log (n)) .

Dans la file d'attente prioritaire, nous aurons juste des éléments avec une fréquence plus élevée en haut.

Extrait :

import java.util.*;
public class Main{
    static class Element{
        int value,freq;
        Element(int value,int freq){
            this.value = value;
            this.freq = freq;
        }
    }
    public static void main(String[] args) {
        sort(new int[]{2,2,4,5,7,6,4,8,3,9,5,7,2});
    }

    public static void sort(int a[]){
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<a.length;++i){
            map.merge(a[i], 1, Integer::sum);
        }

        PriorityQueue<Element> pq = new PriorityQueue<Element>(1000,(c,d) -> (d.freq - c.freq));
        for(Map.Entry<Integer,Integer> m : map.entrySet()){
            pq.offer(new Element(m.getKey(),m.getValue()));
        }

        while(!pq.isEmpty()){
            Element e = pq.poll();
            System.out.println(e.value + " => " + e.freq);
        }
    }
}

Démo: https://onlinegdb.com/HJpdDX7bI

Voici encore une autre solution:

public static void sort(int[] a) {
    Map<Integer, Integer> hs = new HashMap<>();
    for (int i = 0; i < a.length; i++) {
        Integer j = a[i];
        if (hs.containsKey(j)) {
            hs.put(j, hs.get(j) + 1);
        } else {
            hs.put(j, 1);
        }
    }
    List<Map.Entry<Integer,Integer>> list = new ArrayList<>(hs.entrySet());
    Collections.sort(list, (x,y)->{
        int r = x.getValue().compareTo(y.getValue());
        if (r == 0) {
            r = x.getKey().compareTo(y.getKey());
        }
        return r;
    });
    for (Map.Entry<Integer, Integer> entry : list) {
        System.out.println(entry.getKey() + ": " + entry.getValue());
    }
}