Temu Duga Pengekodan: Bagaimanakah anda akan mengembalikan K perkataan paling kerap?

Gesaan dan konteks

Diberikan satu tatasusunan words dan integer k, kembalikan k perkataan yang paling kerap. Selesaikan ikatan mengikut urutan leksikografik menaik.

Temu duga ini memberi tumpuan kepada pengekalan set calon bersaiz k dan memutuskan sama ada punca heap mewakili calon yang paling teruk atau terbaik. Java hanya digunakan untuk menunjukkan pembanding; algoritma ini tidak bergantung pada bahasa tertentu.

Perkara yang diuji oleh penemu duga

Pengiraan

Gunakan peta cincang (hash map) untuk mengira setiap perkataan dan membezakan panjang tatasusunan n daripada kiraan perkataan unik m.

Peraturan pengisihan

Kekerapan lebih tinggi menang; kekerapan sama menggunakan urutan leksikografik yang lebih kecil. Punca min-heap hendaklah menjadi calon yang lebih teruk supaya entri berlebihan boleh disingkirkan.

Kekompleksan

Pengisihan penuh ialah O(m log m). Heap bersaiz k ialah O(n + m log k), berguna apabila k jauh lebih kecil daripada bilangan perkataan unik.

Ketepatan

Terangkan mengapa susunan heap untuk penyingkiran berbeza daripada susunan output akhir: heap menyingkirkan calon yang paling teruk, manakala jawapan mesti menyenaraikan calon yang terbaik dahulu.

Soalan penjelasan untuk ditanya

Adakah perkataan dalam huruf kecil bahasa Inggeris dan sensitif huruf besar/kecil (case-sensitive)?
Adakah k dijamin antara 1 dan bilangan perkataan unik?
Adakah susunan leksikografik mengikut ASCII, Unicode, atau lokal perniagaan?
Adakah input mesti diproses sebagai penstriman (stream)?
Adakah output mesti stabil, atau sebarang susunan boleh diterima?
Bolehkah kekerapan melebihi integer 32-bit?

Rangka kerja jawapan 30 saat

"Saya akan mengira kekerapan dengan peta cincang. Bagi setiap perkataan unik, saya mengekalkan min-heap bersaiz k yang puncanya ialah calon yang lebih teruk: kekerapan lebih rendah, atau urutan leksikografik lebih besar jika berlaku ikatan. Selepas memasukkan, saya mengeluarkan (pop) apabila heap melebihi k. Akhir sekali, saya mengeluarkan entri heap dalam susunan kekerapan menurun dan susunan leksikografik menaik. Kos pengiraan ialah O(n), penyelenggaraan heap O(m log k), dan ruang ialah O(m)."

Analisis mendalam langkah demi langkah

Langkah 1: Kira kekerapan

Petakan setiap perkataan kepada bilangannya. Log penstriman mungkin menggunakan agregasi luaran atau pembilang anggaran, tetapi masalah ini menganggap peta perkataan unik muat dalam memori.

Langkah 2: Tentukan calon paling teruk

Calon A lebih teruk daripada B apabila A mempunyai kekerapan yang lebih rendah; jika seri, A mempunyai susunan leksikografik yang lebih besar. Pembanding meletakkan calon tersebut di punca heap.

Langkah 3: Kekalkan saiz k

Masukkan setiap entri daripada peta kekerapan dan lakukan pop apabila heap melebihi k. Oleh itu, heap mengekalkan k entri yang paling berkemungkinan tergolong dalam jawapan akhir.

Langkah 4: Hasilkan output

Pop daripada heap berjalan daripada yang paling teruk kepada yang lebih baik, jadi ia tidak boleh dikembalikan secara terus. Terbalikkan entri yang dikumpul atau susunnya dengan kekerapan menurun dan leksikografik menaik.

Langkah 5: Buktikan ketepatan

Setiap kali saiz melebihi k, singkirkan ahli paling teruk daripada set semasa. Ahli tersebut tidak boleh mengatasi mana-mana daripada k ahli yang dikekalkan. Melalui induksi, heap akhir mengandungi Top K global.

Langkah 6: Kendalikan sempadan

Uji k=1, kekerapan sama, satu perkataan unik, banyak pendua, dan k=m. Pembanding tidak boleh menterbalikkan ikatan secara tidak sengaja.

Model jawapan berkualiti tinggi

java

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> count = new HashMap<>();
        for (String word : words) {
            count.merge(word, 1, Integer::sum);
        }

        PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> {
            int byFrequency = Integer.compare(count.get(a), count.get(b));
            if (byFrequency != 0) return byFrequency;
            return b.compareTo(a); // larger lexicographic value is worse
        });

        for (String word : count.keySet()) {
            heap.offer(word);
            if (heap.size() > k) heap.poll();
        }

        List<String> answer = new ArrayList<>();
        while (!heap.isEmpty()) answer.add(heap.poll());
        Collections.reverse(answer);
        return answer;
    }
}

Kos pengiraan ialah O(n). Dengan m perkataan unik, operasi heap menelan kos O(log k), untuk jumlah masa O(n + m log k) dan ruang O(m).

Kesilapan biasa

Meletakkan calon terbaik di punca heap → jawapan yang betul disingkirkan → letakkan calon paling teruk di punca.
Menterbalikkan pembanding ikatan → susunan output salah → kekalkan perkataan yang lebih kecil secara leksikografik dahulu pada kekerapan yang sama.
Mengembalikan pop heap secara terus → output berjalan daripada paling teruk kepada terbaik → terbalikkan atau lakukan isihan akhir.
Mendakwa O(n log k) selepas pengisihan penuh → kekompleksan adalah palsu → pengisihan penuh menelan kos O(m log m).
Hanya menguji kekerapan yang berbeza → tingkah laku ikatan tidak diuji → sertakan semua kekerapan yang sama dan banyak kes seri.
Mengabaikan k=m → penyingkiran yang tidak perlu atau ralat sempadan → benarkan heap mengandungi semua perkataan unik.
Menggunakan susunan bergantung pada lokal secara tidak sengaja → hasil berbeza mengikut persekitaran → nyatakan susunan yang diperlukan secara eksplisit.
Menamakan peta cincang tanpa analisis ruang → skala menjadi tidak jelas → nyatakan kekompleksan n, m, dan k.

Soalan susulan dan jawapan

Soalan susulan 1: Adakah anda masih menggunakan heap apabila k menghampiri m?

Pengisihan penuh mungkin mempunyai pemalar yang lebih baik dan kod yang lebih mudah. Heap kekal sah, tetapi O(m log k) menghampiri O(m log m).

Soalan susulan 2: Bagaimana jika input adalah penstriman tanpa batasan?

Kiraan tepat masih memerlukan keadaan (state). Gunakan tetingkap (windows), agregasi luaran, atau anggaran; Top K yang tepat memerlukan keadaan kekerapan yang dikekalkan secukupnya.

Soalan susulan 3: Bagaimana jika perkataan unik melebihi memori?

Lakukan pemetakan cincang (partition-hash) ke cakera, kira setiap petak, dan gabungkan calon, atau gunakan isihan luaran. Jangan muatkan tatasusunan penuh ke dalam memori.

Soalan susulan 4: Bagaimanakah anda menyokong perkataan yang tidak sensitif huruf besar/kecil?

Normalkan dengan lokal eksplisit sebelum mengira. Tentukan sama ada output mengekalkan ejaan asal dan elakkan mengira bentuk yang setara sebanyak dua kali.

Soalan susulan 5: Bagaimanakah anda menguji pembanding?

Buat penegasan (assert) pada kekerapan yang sama dengan urutan leksikografik bertentangan, k=1, k=m, dan input dengan banyak pendua; bandingkan kes rawak dengan rujukan isihan penuh.

Sumber 1: LeetCode 692

Masalah ini mentakrifkan kekerapan menurun, ikatan leksikografik menaik, dan susulan O(n log k), menetapkan output dan sasaran kekompleksan.

Sumber 2: NeetCode Top K

NeetCode menunjukkan pendekatan peta kekerapan dan Top K serta menekankan pembanding dan pertukaran antara heap dan isihan.

Sumber 3: Oracle PriorityQueue

Oracle mendokumentasikan susunan PriorityQueue mengikut susunan semula jadi atau Comparator, menyokong pembanding min-heap tersuai dan semantik poll.