Top K Tez-tez Sözlər LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance Expedia Facebook Goldman Sachs google microsoft Nvidia Kahin PayPal Salesforce İki Sigma Über Viza Arzu Yahoo
TwitchBaxılıb 30

Problem bəyanat

Top K Tez-tez Sözlər LeetCode Həlli – Bir sıra sətirlər nəzərə alınmaqla words və tam ədəd k, qayıt bu k ən çox rast gəlinən simlər.

Cavabı qaytarın sıralandı by tezliyi ən yüksəkdən aşağıya. Eyni tezlikli sözləri özlərinə görə sıralayın leksikoqrafik sifariş.

misal

Test işi 1:

Input:

sözlər = [“i”,”love”,”leetcode”,”i”,”love”,”kodlaşdırma”]

k = 2

Çıxış:

["Mən sevirəm"]

Izahat

"i" və "sevgi" ən çox yayılmış iki sözdür. Qeyd edək ki, "i" daha aşağı əlifba sırasına görə "sevgi"dən əvvəl gəlir.

Yanaşma:

bu, 2 şərt üçün müqayisə strukturudur:

1- azalan sıraya riayət edin (prioritet növbədə ən yüksək tezlik birincidir)

2- əgər iki söz eynidirsə tezliyi, sonra iki sətri müqayisə edin:

Bu sual a saxlamaqla həll edilə bilər HashMap K Top Tez-tez Sözləri əldə etmək üçün sözlərin tezliyini və prioritet növbəni (min-yığın) saymaq.

Sözü və onun tezliyini saxlamaq üçün sinif təyin edin. Obyekti yığında çeşidləmək və saxlamaq üçün minHeap tərəfindən istifadə edilən compareTo metodunu tətbiq edin. Bu sualı həll etməyin hiyləsi bu müqayisə üsulundadır.

Sual bizdən yuxarıdakı sözlərin eyni tezliyə malik olduqları halda leksikoqrafik ardıcıllıqla qaytarmağı tələb edir. Beləliklə, min-yığında sözləri elə saxlayaq ki, eyni tezliyə malik olan sözlər leksikoqrafik sıranın tərsinə yığılsın ki, hər dəfə eyni tezliyə malik sözlə rastlaşanda, gələn sözü çıxaraq. ardıcıllıqla sonuncu.

Aşağıdakı icrada mən istifadə edirəm Map.Entry sinifi intensiv. Beləliklə, saxlamaq <word, frequency> kodun səmərəliliyini artıraraq, ehtiyac duyduğum zaman məlumatları birlikdə toplayıram.

Üst K Tez-tez Sözlər üçün Kod

C ++ Proqramı

class compare{
    public:
        bool operator()(pair<int,string> pair1,pair<int,string> pair2){
          
            if(pair1.first != pair2.first)
                return pair1.first < pair2.first;
            else
                return pair1.second>=pair2.second;
        }
    
};

class Solution {
public:
       vector<string> topKFrequent(vector<string>& words, int k) {
       priority_queue<pair<int,string>,vector<pair<int,string>>,compare> pq;
       unordered_map<string,int> umap;
       
       for(string word:words)
           umap[word]++;
        
       for(auto itr=umap.begin();itr!=umap.end();itr++)
       {
           pq.push(make_pair(itr->second,itr->first));
       }
        
       vector<string> freqWords;
       
        while(k>0)
        {
            freqWords.push_back(pq.top().second);
            pq.pop();
            k--;
        }
        
        return freqWords;
    }
};

Java Proqramı

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            if (map.get(word) == null) {
                map.put(word, 0);
            }
            map.put(word, map.get(word) + 1);
        }
        
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<Map.Entry<String, Integer>>(new Comparator<Map.Entry<String, Integer>>() {
      @Override
      public int compare(Map.Entry<String, Integer> e1, Map.Entry<String, Integer> e2) {
        if (e1.getValue() != e2.getValue()) {
          return e1.getValue().compareTo(e2.getValue());
        } else {
          return e2.getKey().compareTo(e1.getKey());
        }
      }
        }); 
        
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            minHeap.offer(entry);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        List<String> ret = new ArrayList<>();
        while (!minHeap.isEmpty()) {
        	ret.add(minHeap.poll().getKey());
        }
        
        Collections.reverse(ret);
        return ret;
    }
}

Top K Tez-tez Sözlər LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi: O(nlogK) hara n girişin uzunluğudur words[] serial.
Bu Heap ölçüsündə olması ilə əlaqədardır K, və biz cəmi daxil/çıxış qoyduq n dəfə.

Kosmik mürəkkəblik: O(n) istifadə olunan xəritəyə görə.

Translate »