Поредај елементе по учесталости


Ниво тешкоће Лако
Често питани у амазонка пророчанство Зохо Зицус
Ред Хасхинг сортирање

Изјава о проблему

Добија се поредак целих бројева, у њему се понављају неки бројеви. Изјава о проблему тражи испис броја у низу у опадајућем редоследу у складу са њиховом учесталошћу, односно разврставањем елемената по учесталости.

Пример

arr[]={3,4,3,1,2,9,2,9,2,5 }
2 2 2 3 3 9 9 4 1 5

Објашњење: Овде одштампани број смањује се редоследом њихове учесталости. Број 2 има максималну фреквенцију, па је прво одштампан, број 3 и број 9 имају исте фреквенције као 2, али 3 долази на прво место по редоследу, па је одштампан пре 9, а затим 4, 1 и 5 са ​​фреквенцијом 1.

 

Алгоритам за сортирање елемената по учесталости

1. Declare a map.
2. Count and store the frequency of each number of an array into the map.
3. Select the keys with greater frequencies.
4. Get that frequency into val.
5. Print that key, its frequency number of times that is val.

Објашњење

Дали смо целобројни низ. Затражили смо штампање низа у опадајућем редоследу фреквенције. Ако у низу било који број долази највише к број пута, тада би тај број требало да буде одштампан x број пута прво, а затим након низа долази број који има фреквенцију мању од к. За то ћемо користити хеширање. За то ћемо користити мапу.

Користићемо мапу, прећи ћемо низ. Затим пребројите и сачувајте све бројеве у низу са његовом фреквенцијом на мапи. Ако је било који елемент нов на мапи, направите место за његов унос. Затим означите његову фреквенцију као 1. Ако већ постоји, узмите је и повећајте фреквенцију за 1 и поново је притисните истим бројем. Тада можемо узети било коју структуру података да задржи наше резултујуће податке када сортирамо број према њиховој учесталости.

Прелазићемо по мапи. Након тога ћемо сортирати низ према њиховој фреквенцији, а све мање значи да је број са вишом фреквенцијом на првом месту, а такође и број са сличном фреквенцијом у редоследу у сортираном низу као у оригиналном низу. Изаберите сваки кључ и његову вредност и тај кључ ћемо одштампати Вал број пута. Ако не желимо да га директно одштампамо, а затим га складиштимо у било који тип података, овде смо користили СтрингБуффер или вектор за чување података, а касније можемо да одштампамо вредности тог типа података. Аутоматски смо га сортирали тако да имамо максималну фреквенцију и исписујемо ту кључну фреквенцију колико пута. И тако сортирамо елементе по учесталости.

Поредај елементе по учесталости

код

Ц ++ код за сортирање елемената по учесталости

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;
unordered_map<int, int> map1;
bool sortFrequency(const pair<int, int>& a, const pair<int, int>& b)
{
    if (a.second == b.second)
    {
        return map1[a.first] < map1[b.first];
    }
    return a.second > b.second;
}
void sortByFreq(int a[], int n)
{
    unordered_map<int, int> MAP;
    vector<pair<int, int> > vec;
    for (int i = 0; i < n; ++i)
    {
        MAP[a[i]]++;
        if (!map1.count(a[i]))
            map1[a[i]] = i + 1;
    }
    copy(MAP.begin(), MAP.end(), back_inserter(vec));
    sort(vec.begin(), vec.end(), sortFrequency);
    for (int i = 0; i < vec.size(); ++i)
        for (int j = 0; j < vec[i].second; ++j)
            cout << vec[i].first << " ";
}
int main()
{
    int arr[] = {3,4,3,1,2,9,2,9,2,5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    sortByFreq(arr, n);
    return 0;
}
2 2 2 3 3 9 9 4 1 5

 

Јава код за сортирање елемената по учесталости

import java.io.IOException;
import java.util.*;

class sortByFrequency
{
    public static StringBuffer sortFrequency(int arr1[], int l1)
    {
        Map<Integer, Integer> sortMap = frequencyMap(arr1, l1);
        StringBuffer output = new StringBuffer();

        sortMap.entrySet().stream()
        .sorted(Map.Entry.<Integer, Integer> comparingByValue().reversed())
        .forEach(e ->
        {
            int key = e.getKey();

            int val = e.getValue();

            for (int i = 0; i < val; i++)
            {
                output.append(key + " ");
            }
        });

        return output;
    }
    private static Map<Integer, Integer> frequencyMap(int[] arr, int l1)
    {
        Map<Integer, Integer> FrequencyMap = new LinkedHashMap<>();
        for (int i = 0; i < l1; i++)
        {
            if (FrequencyMap.containsKey(arr[i]))
            {
                FrequencyMap.put(arr[i], FrequencyMap.get(arr[i]) + 1);
            }
            else
            {
                FrequencyMap.put(arr[i], 1);
            }
        }
        return FrequencyMap;
    }
    public static void main(String[] args)
    {
        int arr[] = { 3,4,3,1,2,9,2,9,2,5 };
        System.out.println(sortFrequency(arr, arr.length));
    }
}
2 2 2 3 3 9 9 4 1 5

Анализа сложености

Сложеност времена

О (н + м Лог м) где „Н“ је укупан број елемената у низу и "М" је укупан број различитих елемената у низу. Млогм долази од сортирања м елемената.

Сложеност простора

Пошто смо користили мапу и низ за чување н елемената које имамо Он) где „Н“ је број елемената у низу.