Aiuto con trending

Aiuto
1

Buongiorno a tutti!

Sto provando a risolvere il problema trending e penso di aver capito logicamente come risolverlo, ma con le strutture che sto usando vado in TLE.

Ecco il mio codice che per ora passa i primi tre subtask.

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;

public class trending {

    record Hashtag(String name, int occurrences) {
    }

    // Comparatore personalizzato per ordinare in base ai valori e alle chiavi
    static class HashtagComparator implements Comparator<Hashtag> {

        @Override
        public int compare(Hashtag o1, Hashtag o2) {
            if (o2.occurrences == o1.occurrences) {
                return String.CASE_INSENSITIVE_ORDER.compare(o1.name, o2.name);
            } else {
                return Integer.compare(o2.occurrences, o1.occurrences);
            }
        }
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        int N = in.readInt();
        int T = in.readInt();

        String[] hashtagsName = new String[N];

        for (int i = 0; i < N; i++) {
            hashtagsName[i] = in.readString();
        }

        for (int i = 0; i + T - 1 < N; i++) {

            HashMap<String, Integer> trendingMap = new HashMap<>();
            for (int j = 0; j < T; j++) {
                String hashtag = hashtagsName[i + j];
                if (!trendingMap.containsKey(hashtag)) {
                    trendingMap.put(hashtag, 1);
                } else {
                    trendingMap.put(hashtag, trendingMap.get(hashtag) + 1);
                }
            }

            Hashtag[] hashtags = new Hashtag[trendingMap.size()];
            int index = 0;
            for (HashMap.Entry<String, Integer> entry : trendingMap.entrySet()) {
                hashtags[index++] = new Hashtag(entry.getKey(), entry.getValue());
            }

            Arrays.sort(hashtags, new HashtagComparator());

            System.out.println(hashtags[0].name);
        }

    }
}

Penso che la parte più lenta sia copiare i valori dalla mappa all’array e poi ordinarlo.

Avevo in mente di provare ad usare una sorted map, ma così potrei ordinare solo le chiavi, non anche i valori?

Qualche tip?

2

PS:
InputReader è Scanner, solo più veloce.
Non attribuirei ad essa il TLE.

3

In c++ puoi avere una struttura di questo tipo per ordinare secondo la chiave e, anche, per un set di valori:

map<int, set<int>>

o per il task in oggetto:

map<int, set<string>>

Anche in java c’è una struttura equivalente.

4

Ciao!

Ho risolto il problema e ora passa tutti i test, ma non ho usato nessuna mappa con chiave intera e come valore un set di stringhe.

Ho tenuto una hashmap che conta quante volte ho trovato un hashtag nell’intervallo e un sortedset di tipo Hashtag (su cui applico il comparator) che aggiorno ad ogni modifica della mappa.

Non potendo modificare direttamente il sortedset, prima rimuovo l’elemento interessato, poi aggiorno il valore e lo reinserisco.

Credo che esistano soluzioni migliori.
Potresti spiegarmi meglio come hai usato la mappa?

Allego soluzione per chiarezza:

static class Hashtag implements Comparable<Hashtag> {
        String name;
        int count;

        Hashtag(String name, int count) {
            this.name = name;
            this.count = count;
        }

        @Override
        public int compareTo(Hashtag other) {
            if (this.count != other.count) {
                return Integer.compare(other.count, this.count); // Ordina per conteggio decrescente
            }
            return this.name.compareTo(other.name); // Ordina lessicografica mente in caso di parità
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Hashtag hashtag = (Hashtag) o;
            return count == hashtag.count && Objects.equals(name, hashtag.name);
        }
    }

    public static void main(String[] args) {

        InputReader in = new InputReader(System.in);
        int N = in.readInt();
        int T = in.readInt();

        String[] hashtags = new String[N];
        Map<String, Integer> map = new HashMap<>();
        SortedSet<Hashtag> queue = new TreeSet<>();

        for (int i = 0; i < N; i++) {
            hashtags[i] = in.readString();
        }

        for (int ptrSx = 0, ptrDx = 0; ptrDx < N; ptrDx++) {
            String toAdd = hashtags[ptrDx];

            if (!map.containsKey(toAdd)) {
                map.put(toAdd, 1);
                queue.add(new Hashtag(toAdd, 1));
            } else {
                queue.remove(new Hashtag(toAdd, map.get(toAdd)));
                map.put(toAdd, map.get(toAdd) + 1);
                queue.add(new Hashtag(toAdd, map.get(toAdd)));
            }

            if (ptrDx - ptrSx == T - 1) {
                System.out.println(queue.first().name);

                String toRemove = hashtags[ptrSx++];
                queue.remove(new Hashtag(toRemove,map.get(toRemove)));
                map.put(toRemove, map.get(toRemove) - 1);

                if (map.get(toRemove) == 0) {
                    map.remove(toRemove);
                } else {
                    queue.add(new Hashtag(toRemove, map.get(toRemove)));
                }
            }
        }
    }