Elementləri Frekansa görə sırala II

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Kahin Zoho Zikus
Geyim Hashing HashMap çeşidləyiciBaxılıb 269

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

“Elementləri Tezliklə Sırala II” problemində bir sıra verdik []. Sırala array elementlərin tezliyinə görə ilk növbədə daha yüksək tezlikli element, sonra başqaları gəlir.

Giriş Formatı

Bir n tam ədədi olan ilk və yalnız bir sətir.

Boşluqla ayrılmış n tam ədədi ehtiva edən ikinci sətir.

Çıxış formatı

Elementlərin tezliyi əsasında sıralanmış massivi ifadə edən boşluqla ayrılmış n tam ədədi ehtiva edən ilk və yalnız bir sətir.

Məhdudiyyətlər

  • 1 <= n <= 10 ^ 5
  • 1 <= a [i] <= 10 ^ 9

misal

7
1 4 4 4 2 2 7
4 4 4 2 2 1 7

Explanation: Burada 4-ün frekansı 3-dür, 2-nin frekansı 2-dir və 1,7-in frekası 1-dir. Beləliklə, sıralama sırası 4, 4, 4, 2, 2, 1, 7-dir.

Alqoritm

  1. Bütün elementləri və onların saylarını bir hashə əlavə edirik. Bu addım n (element) sayı olduğu O (n) vaxt aparır.
  2. Haşın məzmununu bir massivə (və ya vektora) kopyalayırıq və sayma görə sıralayırıq. Bu addım, m-nin fərqli elementlərin ümumi sayı olduğu O (m log m) vaxtını alır.
  3. Tezlik eynidirsə, elementlərin sırasını qorumaq üçün açarın sıra elementləri və indeks kimi dəyəri olan başqa bir hash istifadə edirik. Tezlik iki element üçün eynidirsə, elementləri indeksə görə sıralayın.

Həyata keçirilməsi

C ++ Proqramı, Elementləri Frekans II-ə görə çeşidləyəcək

#include <bits/stdc++.h>
using namespace std;

bool sortByVal(const pair<int, int>& a, const pair<int, int>& b)
{
    if (a.second == b.second) 
  {
      return a.first < b.first;
  }
  return a.second > b.second;
}

vector<int>sortfreq(int a[], int n)
{
    vector<int>res;
    unordered_map<int, int> m;
    vector<pair<int, int> > v;
    for (int i = 0; i < n; ++i) 
    {
        m[a[i]]++;	 
    }
    copy(m.begin(), m.end(), back_inserter(v));
    sort(v.begin(), v.end(), sortByVal);
    for (int i = 0; i < v.size(); ++i) 
    {
        while(v[i].second--)
        {
            res.push_back(v[i].first);
        }
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    vector<int>res;
    res = sortfreq(a,n);
    for(auto u: res)
    {
        cout<<u<<" ";
    }
    return 0;
}
8
1 4 4 2 2 2 8 8
2 2 2 4 4 8 8 1

Elementləri Frekans II üzrə Sıralamaq üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n) + O (m Giriş m) burada n - elementlərin ümumi sayı və m - fərqli elementlərin ümumi sayı.

Kosmik Mürəkkəblik

O (n) cavabı saxlamaq üçün bu qədər yer yaradırıq.

Crack Sistemi Dizayn Müsahibələri
Translate »