Mündəricat
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.
