K Removals Leetcode Həllindən sonra Unikal Tam Ədədlərin Ən Az Sayı

Problem bəyanat

The K Silindikdən sonra Unikal Tam Ədədlərin Ən Az Sayı LeetCode Həlli – “K silindikdən sonra unikal tam ədədlərin ən az sayı” sizə tam və tam ədədlər massivi verildiyini bildirir k. Tapın unikal tam ədədlərin ən az sayı çıxardıqdan sonra dəqiq k elementləri.

Misal:

Pin

 

Input:  arr = [5,5,4], k = 1

Output: 1

Explanation:

• k = 1 olduğundan, biz tam olaraq 1 elementi çıxaracağıq.
• Tək 5-in çıxarılması massivi [5,4] kimi verəcəkdir. Beləliklə, bir sıra unikal elementlər 2-dir.
• Tək 4-in çıxarılması massivi [5,5] kimi verəcəkdir. Beləliklə, bir sıra unikal elementlər 1-dir.
• Beləliklə, 4-ün çıxarılması optimaldır, çünki o, 1-ə bərabər unikal elementlərin minimum sayını verir.
• Cavab 1-dir.

Input:  arr = [4,3,1,1,3,3,2], k = 3

Output: 2

Explanation:

• k = 3 olduğundan biz giriş massivindən tam olaraq üç elementi siləcəyik ki, bir sıra unikal elementlər minimuma endirilsin.
• Asanlıqla müşahidə edə bilərik ki, [4,2,1]-in çıxarılması dəqiq 2 verəcək minimum olan fərqli elementlər cavab mümkündür.

Yanaşma

Idea:

1. Bu problemi səmərəli həll etmək üçün əsas fikir istifadə etməkdir (Acgöz yanaşma).
2. Bütün saxla unikal elementlərin tezlikləri verilmiş massivdən tezlik cədvəli.
3. Çünki məcburuq minimuma endirmək fərqli elementlərin sayı k elementi sildikdən sonra, verilmiş massivdə minimum tezlikə malik olan elementlərdən başlayacağıq.
4. Deməli, biz lazımdır unikal elementləri sıralayın və onların tezlikləri azalmayan sifariş onların tezlikləri.
5. Minimum tezliyə malik elementlərlə başlayın və minimum tezliklə K dəyərini azaldın və cari elementi atın. Eyni addımı k müsbət olana qədər təkrarlayın.
6. Yuxarıdakı əməliyyatlardan sonra qalan bir sıra fərqli elementlər k müsbət olana qədər təkrarlanır, cavabımızdır.

Kodu

K sildikdən sonra C++ Unikal Tam Ədədlərin Ən Az Sayı Sim Leetcode Həlli:

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int,int> freq;
        for(auto& num:arr){
            freq[num]++;
        }
        vector<pair<int,int>> store;
        for(auto& x:freq){
            store.push_back({x.second,x.first});
        }
        sort(store.rbegin(),store.rend());
        while(k>0){
            int required = min(k,store.back().first);
            k-=required;
            store.back().first-=required;
            
            if(!store.back().first){
                store.pop_back();
            }
        }
        return store.size();
    }
};

 

K sildikdən sonra Java Ən az unikal tam ədədlər Leetcode Həlli:

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int a : arr){
            freq.put(a, 1 + freq.getOrDefault(a, 0));
        }
        int len = freq.size();
        TreeMap<Integer, Integer> occ = new TreeMap<>();
        for (int v : freq.values()){
            occ.put(v, 1 + occ.getOrDefault(v, 0));
        }
        while(k>0){
            Map.Entry<Integer,Integer> entry = occ.pollFirstEntry();
            if(k-entry.getKey()*entry.getValue()>=0){
                k -= entry.getKey()*entry.getValue();
                len -= entry.getValue();
            }
            else{
                return len - k / entry.getKey();
            }
        }
        return len;
    }
}

K silindikdən sonra ən az unikal tam ədədlər üçün mürəkkəblik təhlili Leetcode Solution

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O(N + MlogM + K) burada N = giriş massivinin uzunluğu və M = unikal elementlərin sayı.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (M), burada M = giriş massivindəki unikal elementlərin sayı.