Frekans Leetcode Çözümünü artıraraq Array sırala

Problem bəyanat

The Tezliyin artırılması ilə massivi çeşidləyin LeetCode Həlli – “Tezliyi artırmaqla massivi çeşidləyin” sizə tam ədədlər massivi verildiyini bildirir, massivi bu şəkildə sıralayın artan sifariş dəyərlərin tezliyinə əsaslanır. İki və ya daha çox dəyər eyni tezlikə malikdir, biz onları sıralamalıyıq azalan sifariş.

Misal:

Input:  nums = [1,1,2,2,2,3]

Output: [3,1,1,2,2,2]

Explanation:

• 1-in tezliyi 2, 2-nin tezliyi 3, 3-ün tezliyi 1-dir.
• 3-cü element minimum tezliyə malik olduğundan, 3-ün baş verməsi birinci olacaq.
• 1-ci element ikinci minimum tezliyə malikdir, buna görə də 1-ci elementin hadisələri 3-cü elementin baş verməsindən sonra gələcək.
• Beləliklə, 2-ci elementin hadisələri sona çatır.
• Son çeşidlənmiş massiv: [3,1,1,2,2,2].

Input:  nums = [2,3,1,3,2]

Output: [1,3,3,2,2]

Explanation:

• 1-in tezliyi 1, 2-nin tezliyi 2, 3-ün tezliyi 2-dir.
• 1-cü element minimum tezliyə malik olduğundan, 1-ün baş verməsi birinci olacaq.
• Element 2 və Element 3 eyni tezliyə malikdir, 3-ün bütün hadisələri 2-nin bütün hadisələrindən əvvəl gələcək.
• 2-ci elementin baş vermələri massivin sonunda gələcək.
• Son çeşidlənmiş massiv: [1,3,3,2,2].

Yanaşma

Idea:

1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Çeşidləmələr.
2. Birincisi, unikal elementlərin bütün tezliklərini yaddaşda saxlayın Hashmap Bu, səmərəli hash funksiyasından istifadə etsək, O(N) sabit fəza və O(1) vaxt alır.
3. istifadə edərək daxil massivi çeşidləyin lambda funksiyası müqayisə edən:
   1. birinci nömrənin tezliyi ikinci nömrənin tezliyindən ciddi şəkildə azdırsa, doğru qayıt.
   2. hər iki ədədin tezliyi bərabərdirsə, iki ədədi müqayisə edin.
4. Sıralanmış massivi qaytarın.

Kodu

Tezliyi artırmaqla massivi çeşidləyin Leetcode C++ Həlli:

class Solution {
public:
    vector<int> frequencySort(vector<int>& nums) {
        unordered_map<int,int> freq;
        for(auto& num:nums){
            freq[num]++;
        }
        sort(nums.begin(),nums.end(),[&](const int a,const int b){
            if(freq[a]==freq[b]){
                return a>b;
            }
            return freq[a]<freq[b];
        });
        return nums;
    }
};

Tezliyi artırmaqla massivi çeşidləyin Leetcode Java Həlli:

class Solution {
    public int[] frequencySort(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        Arrays.stream(nums).forEach(n -> freq.put(n, freq.getOrDefault(n, 0) + 1));
        return Arrays.stream(nums).boxed().sorted((a,b) -> freq.get(a) != freq.get(b) ? freq.get(a) - freq.get(b) : b - a).mapToInt(n -> n).toArray();
    }
}

Frekans Leetcode həllini artıraraq Sort Dizisi üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O(NlogN).

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (N). Hashmap-də hər bir unikal elementin tezliklərinin saxlanması O(N) Boşluğunu tutur.