አባላትን በድግግሞሽ ደርድር


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን በ Oracle ቮሆ ዚኩስ
ሰልፍ ሃምሽንግ መደርደር

የችግሩ መግለጫ

አንድ ተሰጥቶሃል ደርድር የቁጥር ቁጥሮች ፣ የተወሰኑ ቁጥሮች በውስጡ ይደጋገማሉ። የችግሩ መግለጫ አባላትን እንደ ድግግሞሽ መጠን በቅደም ተከተል በመቀነስ በድርድሩ ውስጥ ያለውን ቁጥር ለማተም ይጠይቃል።

ለምሳሌ

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. 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 የብዙዎች ቁጥር መጀመሪያ እና ከዚያ በኋላ ከ 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

 

አባላትን በድግግሞሽ ለመለየት የጃቫ ኮድ

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (n + m Log m) የት “N” በድርድሩ ውስጥ ያሉት አጠቃላይ ንጥረ ነገሮች ብዛት እና ነው "M" በድርድሩ ውስጥ የተለዩ አካላት ጠቅላላ ብዛት ነው። Mlogm የሚመጣው m አባላትን በመለየት ነው ፡፡

የቦታ ውስብስብነት

እኛ ያሉን ንጥረ ነገሮችን ለማከማቸት ካርታ እና ድርድር ስለተጠቀምን ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።