Sortarea literelor unui cuvânt
Ți se dă un cuvânt format din litere mici ale alfabetului englez. Afișează toate literele care apar în cuvânt, reorganizate astfel încât literele care apar cel mai frecvent să se regăsească la început.
Date de intrare
Pe prima linie se va găsi un singur cuvânt, format din litere mici ale alfabetului englez.
Date de ieșire
Se vor afișa literele din cuvânt, fără spații, de atâtea ori de câte apar în cuvântul inițial, reorganizate după regula de mai sus.
Restricții
Cuvântul poate conține până la 100 000 de caractere.
Dacă există litere care apar de același număr de ori, se vor afișa mai întâi cele mai mici după sortarea alfabetică.
Atenție!
Unele clase și operații sunt lente în Java. Din acest motiv se recomandă folosirea BufferedReader și BufferedWriter.
Concatenarea folosind String e lentă.
Exemplu
Date de intrare
instructiuni
Date de ieșire
iiinnttuucrs
In java va rog frumos o rezolvare, multumesc
Răspunsuri la întrebare
Răspuns:
import java.util.*;
public class Main {
public static void main(String[] args) {
/* datele de intrare, le poți citi de la tastatură */
String dateDeIntrare = "instructiuni";
/* apelăm funcția care ne returnează un dicționar cu frecvențele literelor, am folosit un LinkedHashMap pentru că se păstrează ordinea elementelor în funcție de inserarea lor */
LinkedHashMap<Character, Integer> dictionarFrecvente = creareDictionar(dateDeIntrare);
/* sortăm dicționarul după frecvențe iar dacă au aceleași frecvențe, după ordinea alfabetică a literelor */
dictionarFrecvente = sortareDictionar(dictionarFrecvente);
/*
scoatem cheile și valorile în două liste, pentru instrucțiuni vom avea
[i, n, t, u, c, r, s] (ordinea literelor din cuvânt)
[3, 2, 2, 2, 1, 1, 1] (de câte ori trebuie să apară litera în cuvântul final)
*/
List<Character> listaCaractere = new ArrayList<>(dictionarFrecvente.keySet());
List<Integer> listaFrecvente = new ArrayList<>(dictionarFrecvente.values());
/* după cum observi, tot ce trebuie să facem acum e să creăm cuvântul final */
String cuvantFinal = creareCuvantFinal(listaCaractere, listaFrecvente);
System.out.println(cuvantFinal); /* output: iiinnttuucrs */
}
private static LinkedHashMap<Character, Integer> creareDictionar(String dateDeIntrare) {
LinkedHashMap<Character, Integer> dictionarFrecvente = new LinkedHashMap<>();
/* iterăm pe caracterele din cuvânt, dacă caracterul e prezent în dicționar îi incrementăm valoarea altfel adăugăm caracterul în dicționar cu valoarea 1 */
for (Character caracterCurent : dateDeIntrare.toCharArray()) {
dictionarFrecvente.put(caracterCurent, dictionarFrecvente.containsKey(caracterCurent)
? dictionarFrecvente.get(caracterCurent) + 1
: 1);
}
return dictionarFrecvente;
}
private static String creareCuvantFinal(List<Character> listaCaractere, List<Integer> listaFrecvente) {
/* listaCaractere și listaFrecvente vor avea dimensiuni egale */
int dimensiuneListe = listaCaractere.size();
StringBuilder cuvantFinal = new StringBuilder();
/* pentru fiecare frecvență din listă */
for (int i = 0; i < dimensiuneListe; i++) {
/* o preluăm */
int numarRepetari = listaFrecvente.get(i);
/* și adăugăm la cuvântFinal caracterul curent de numarRepetări ori */
cuvantFinal.append(String.valueOf(listaCaractere.get(i)).repeat(numarRepetari));
}
/* la final returnăm cuvântulFinal sub formă de String */
return cuvantFinal.toString();
}
private static LinkedHashMap<Character, Integer> sortareDictionar(LinkedHashMap<Character, Integer> dictionarFrecvente) {
/* creăm un nou dicționar care va conține cheile sortate */
LinkedHashMap<Character, Integer> dictionarFrecventeSortat = new LinkedHashMap<>();
/* creăm o listă cu Entryurile (elementele) dicționarului */
List<Map.Entry<Character, Integer>> entryList = new LinkedList<>(dictionarFrecvente.entrySet());
/* sortăm lista după următoarele criterii: */
entryList.sort((primulEntry, alDoileaEntry) ->
primulEntry.getValue().compareTo(alDoileaEntry.getValue()) == 0
/* dacă avem aceleași valori (nr. de repetiții) sortăm elementele alfabetic (crescător) */
? primulEntry.getKey().compareTo(alDoileaEntry.getKey())
/* dacă avem nr. diferit de valori (de repetiții) sortăm descrescător */
: alDoileaEntry.getValue().compareTo(primulEntry.getValue()));
/* la final adăugăm elementele sortate în noul dicționar */
for (Map.Entry<Character, Integer> entryCurent : entryList)
dictionarFrecventeSortat.put(entryCurent.getKey(), entryCurent.getValue());
/* pe care-l și returnăm */
return dictionarFrecventeSortat;
}
}