Элементҳоро аз рӯи басомад ҷобаҷо кунед


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon Oracle Зохо Зикус
тартиботи ҳарбӣ Хашм Sorting

Изҳороти мушкилот

Ба шумо як асал шумораи бутун, дар он якчанд рақам такрор карда мешавад. Дар изҳороти масъала дархост карда мешавад, ки шумораи массивро мувофиқи басомади онҳо бо тартиби кам, чоп кунад, яъне унсурҳоро аз рӯи басомад.

мисол

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 маротиба ояд, пас ин рақам бояд чоп карда шавад x миқдори маротиба аввал ва баъд пас аз адади дорои басомади камтар аз х дар пайдарпаӣ меояд. Барои ин, мо ҳешингро истифода мебарем. Мо барои ин харитаро истифода карданӣ ҳастем.

Мо харитаро истифода мебарем, массивро убур хоҳем кард. Пас ҳамаи рақамҳоро дар массив бо басомади он дар харита ҳисоб кунед ва нигоҳ доред. Агар ягон харита дар харита нав бошад, пас барои вуруди он ҷой гузоред. Пас басомади онро ҳамчун 1 қайд кунед. Агар он аллакай мавҷуд бошад, пас басомади онро гиред ва басомади онро 1 зиёд кунед ва дубора бо ҳамон рақам тела диҳед. Пас, мо метавонем ҳама гуна сохтори маълумотро барои нигоҳ доштани маълумоти натиҷавии худ ҳангоми рақамро мувофиқи басомади худ гирем.

Мо харитаро давр мезанем. Пас аз он, мо массивро аз рӯи басомади онҳо ҷудокунӣ менамоем, маънои он ки шумораи дорои басомади баландтар дар ҷои аввал меистад ва инчунин шумораи бо басомади шабеҳ ба тартиб дар массиви ҷудошуда, тавре ки дар массиви аслӣ омадааст, меояд. Мо ҳар як калид ва арзиши онро интихоб мекунем ва мо он калидро чоп карданӣ ҳастем Вал шумораи маротиба. Агар мо намехоҳем онро мустақиман чоп кунем, пас онро дар ягон намуди маълумот нигоҳ дорем, дар ин ҷо мо StringBuffer ё векторро барои нигоҳ доштани маълумот истифода кардем ва баъдтар, мо метавонем ин миқдори намудҳои маълумотро чоп кунем. Ба таври худкор, мо онро ҷобаҷо кардем, то басомади ҳадди аксарро дошта бошем ва ин басомади калидиро чанд маротиба чоп кунем. Ва ҳамин тавр мо унсурҳоро аз рӯи басомад ҷудо мекунем.

Элементҳоро аз рӯи басомад ҷобаҷо кунед

рамз

Коди C ++ барои ҷобаҷогузории унсурҳо аз рӯи басомад

#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

 

Рамзи Java барои ҷобаҷогузории унсурҳо аз рӯи басомад

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

Таҳлили мураккабӣ

Мураккабии вақт

O (n + m Log m) ки дар "Н" шумораи умумии унсурҳои массив аст ва "М" шумораи умумии унсурҳои алоҳида дар массив аст. Млогм аз ҷобаҷогузории m элемент сарчашма мегирад.

Мураккабии фазо

Азбаски мо харита ва массивро барои нигоҳ доштани n элемент истифода кардем Эй (н) ки дар "Н" шумораи унсурҳои массив аст.