Elementləri Baş Sıxlığına görə Sırala

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Kahin Zoho Zikus
Geyim Hashing HashMapBaxılıb 1446

Problem bəyanat

Elementləri baş vermə tezliyi probleminə görə sıraladıq array a []. Massiv elementlərini elə bir şəkildə sıralayın ki, ən çox baş verən element birinci yerə çıxsın. Baş vermə sayı bərabərdirsə, ilk növbədə massivdə görünən ədədi çap edin.

Giriş Formatı

Bir tam dəyər N ehtiva edən birinci sətir.

N tam ədədi olan ikinci sətir.

Çıxış formatı

Giriş sətri elementlərini tək sətirdə çap edin. elə bir şəkildə ki, a [i] tezliyi a [i + 1] tezliyindən böyük və ya bərabərdir.

Məhdudiyyətlər

  • 1 <= N <= 100000
  • -1e9 <= arr [i] <= 1e9

Baş vermə tezliyinə görə Sıralama Elementləri üçün İzahat

Sual iki əsas problemi əhatə edir

  • Tezlik və
  • Qarşıdurmanın həlli üçün sifarişin qorunması.

İki inkişaf etmiş və güclü məlumat quruluşundan istifadə edirik:

MAP  və  MULTIPMAP.

Xəritə dəyər üçün bəzi açarları eşleme xüsusiyyətinə malikdir. Multimap eyni funksiyanı yerinə yetirir, lakin xəritələrə əlavə olaraq açarı sıralanmış qaydada və xüsusi qaydada saxlayır. Tam olaraq tələb etdiyimiz funksiya.

Baş vermə tezliyinə görə elementləri çeşidləmə alqoritmi

1.  Elementləri xəritəyə əlavə edin (xəritə) ).
     a. Əgər onlar yoxdursa, əlavə edin və sayını 1 edin.
     b. Başqa bir şey yenidən meydana gəldiyi üçün dəyər sayını 1 artırın. Xəritə edir cüt.

2.  İndi xəritədən keçin və elementləri bu şəkildə multimap-a əlavə edin:
     a. Xəritəin 2-ci sahəsini, yəni xəritənin tezliyini multimapın açarı kimi et ki, avtomatik olaraq sıralansın.
     b. Multimapdakı hər girişin tutulması üçün ilk dəyəri ikinci ilə eşleyin tezlik üzrə artan sırada.

3. İndi istədiyiniz nəticəni əldə etmək üçün çox xəritəni tərs qaydada keçin.

Həyata keçirilməsi

Hadisələrin Tezliyinə görə Sıralama Elementləri üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
typedef multimap<int, int> MapType;
int main()
{
    int N;
    cin>>N;
    int a[N];
    for(int i=0;i<N;i++)
    {
       cin>>a[i];
    }
    //Map uses the first id as the array element and second as the count of occurrences of the element 
    map<int,int> mp; 
    for(int i=0;i<N;i++)
    {
        //if the array element is present then just increase the count of occurence of it by 1 
        if(mp.find(a[i])!=mp.end()){ 
            mp[a[i]]++;
        }
        else{
            //if the array element is not present in the map already then add it
            mp[a[i]]=1; 
        }
    }
    //it maintains specific order and count  and while inserting makes it sorted
    multimap<int,int> mp2; 
    map<int,int>::iterator it;
    for(it=mp.begin();it!=mp.end();it++){
      //Second becomes the key as we need to sort according to frequency.
      mp2.insert(MapType::value_type(it->second,it->first)); 
    }
    map<int,int>::reverse_iterator itr;
    for(itr=mp2.rbegin();itr!=mp2.rend();itr++)
    {
        //Reverse the multimap and print so that it prints in decreasing order.
        for(int i=0;i<itr->first;i++)
            cout<<itr->second<<"\t";
    }  
    return 0;
}

Hadisələrin Tezliyinə görə Sıralama Elementləri üçün Java Proqramı

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

class SortComparator implements Comparator<Integer> {
    private final Map<Integer, Integer> freqMap;
  
    // Assign the specified map
    SortComparator(Map<Integer, Integer> tFreqMap)
    {
        this.freqMap = tFreqMap;
    }
  
    // Compare the values
    @Override
    public int compare(Integer k1, Integer k2)
    {
  
        // Compare value by frequency
        int freqCompare = freqMap.get(k2).compareTo(freqMap.get(k1));
  
        // Compare value if frequency is equal
        int valueCompare = k1.compareTo(k2);
  
        // If frequency is equal, then just compare by value, otherwise -
        // compare by the frequency.
        if (freqCompare == 0)
            return valueCompare;
        else
            return freqCompare;
    }
}
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> outputArray = new ArrayList<>();
        for (int current : arr) 
        {
            int count = map.getOrDefault(current, 0);
            map.put(current, count + 1);
            outputArray.add(current);
        }
        // Compare the map by value
        SortComparator comp = new SortComparator(map);
        // Sort the map using Collections CLass
        Collections.sort(outputArray, comp);  
        // Final Output
        for (Integer i : outputArray) 
        {
            System.out.print(i + " ");
        }
    }
}
8
2 5 2 8 5 6 8 8
8 8 8 2 2 5 5 6

Baş vermə tezliyinə görə Sıralama Elementləri üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (NlogN), burada N - massivdə mövcud olan elementlərin sayı. Burada elementləri sıralanmış multimapda düzəldirik.

Kosmik Mürəkkəblik

O (N), çünki burada N-ə qədər maksimum ölçülü multimap və xəritə istifadə edirik.

References

Translate »