የድግግሞሽ ሌቲኮድ መፍትሄን በመጨመር ድርድር


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ eBay ቴሊዮ
ሰልፍ ሃሽ ማፕ መደርደር

የችግሩ መግለጫ

የቁጥር ቁጥሮች ብዛት ከተሰጠ ፣ በእሴቶቹ ድግግሞሽ ላይ በመመርኮዝ ቅደም ተከተሉን በመደርደር ይመድቡ። ብዙ እሴቶች ተመሳሳይ ድግግሞሽ ካላቸው በሚቀንሱ ቅደም ተከተል ያድርጓቸው።

ለምሳሌ

nums = [1,1,2,2,2,3]
[3,1,1,2,2,2]

ማብራሪያ:

'3' 1 ድግግሞሽ አለው ፣ '1' ድግግሞሽ 2 ፣ እና '2' ደግሞ 3 ድግግሞሽ አለው።

nums = [2,3,1,3,2]
[1,3,3,2,2]

ማብራሪያ:

'2' እና '3' ሁለቱም የ 2 ድግግሞሽ አላቸው ፣ ስለሆነም በሚቀንሱ ቅደም ተከተሎች ይመደባሉ።

ቀረበ

በመጀመሪያ በዚህ ችግር ውስጥ የእያንዳንዱን ንጥረ ነገር ድግግሞሽ መቁጠር አለብን ፡፡ ለዚህም እኛ ሀ ሃሽ ካርታ በጃቫ ውስጥ ወይም ያልተስተካከለ ስብስብ በ c ++ ውስጥ። አሁን የውጤታችን ድርድር መጀመሪያ ከፍተኛ ድግግሞሽ ያላቸውን እነዚያን ንጥረ ነገሮች እንዲይዝ እንፈልጋለን።
ለዚህም ቀደም ሲል በካርታው ላይ ባስቀመጥነው አጠቃላይ ድግግሞሽ መሠረት የተሰጠውን የግብዓት ድርድር አሁን መደርደር እንችላለን ፡፡

አሁን እኛ ከሥራው ውጭ ማነፃፀሪያ መሥራት አለብን ፡፡ እዚህ ሁለት አባላትን እናነፃፅራለን (ሀ እና ለ እንበል) የእያንዳንዱን ንጥረ ነገር ድግግሞሽ እናውቃለን ፡፡ ስለዚህ የ A ድግግሞሽ ከ b የሚበልጥ ከሆነ ለድርድሩ ከ b በፊት ያስቀምጡ። የሚቀጥለው ጉዳይ የ ‹ሀ› እና ‹‹››››››››››››››››››››››››››››››››››››› +››››››››››››››››››››››››››››››››››››››››XNUMX“ ‘“ ‘’ ’’ ‘’ ’’ ’’ ’’ ’’ ’’ ’’ ’’ ’’ ’’ ’’ ’’ ’’ ’’ ’’ ’’ ’’ ’’ ’’ ’’ ’’ ”/” / ”/’ / ’’ ’ድግግሞሽ ተመሳሳይ ከሆነ የሚቀጥለው ጉዳይ ይሆናል ከዚያ ከፍ ያለ እሴት ያለው ያንን ንጥረ ነገር ያስቀድሙ ለምሳሌ:

መያዣ 1የድግግሞሽ ሌቲኮድ መፍትሄን በመጨመር ድርድር

መያዣ 2የድግግሞሽ ሌቲኮድ መፍትሄን በመጨመር ድርድር

አልጎሪዝም

  • የሃሽ ካርታ ይፍጠሩ ፡፡
  • አንድ ዙር ያሂዱ እና ለእያንዳንዱ ንጥረ ነገር በካርታው ውስጥ የዚያን ንጥረ ነገር ብዛት በ 1 ይጨምሩ።
  • አሁን በካርታው ውስጥ የተከማቸውን ብዛት በመጠቀም ሁለት ኢንቲጀሮችን ለማነፃፀር የንፅፅር ተግባር ያድርጉ ፡፡ ሁለት አባላትን ያነፃፅሩ እና ከላይ እንደተጠቀሰው ቅደም ተከተላቸውን ይወስናሉ ፡፡
  • ይህንን ንፅፅር በመጠቀም የተሰጠውን ድርድር ለይ።
  • የተደረደረውን ድርድር ይመልሱ።

አፈጻጸም

ድግግሞሽ Leetcode መፍትሄን በመጨመር ለ ‹ድርድር› C ++ ፕሮግራም

#include <bits/stdc++.h>
using namespace std;

bool comp(pair<int,int> p1,pair<int,int> p2)
{
    if(p1.second == p2.second) return p1.first > p2.first;
    return p1.second < p2.second;
}

vector<int> frequencySort(vector<int>& nums) 
{
    unordered_map<int,int> m;
    for(auto x:nums) m[x]++;

    vector<pair<int,int> > v;

    for(auto p:m) v.push_back(p);

    sort(v.begin(),v.end(), comp);

    vector<int> res;
    for(auto p:v)
    {
        while(p.second--)
            res.push_back(p.first);
    }

    return res;        
}

int main() 
{
    vector<int> nums = {2,3,1,3,2};
    for(int x: frequencySort (nums))
        cout<<x<<" ";
    return 0; 
}
1 3 3 2 2

ድግግሞሽ የሌትኮድ መፍትሄን በመጨመር የጃቫ ፕሮግራም ለድርድር

import java.util.*;
import java.lang.*;

class Comp implements Comparator<Integer>{
    Map<Integer,Integer>map=Rextester.map;
    public int compare(Integer a,Integer b){
        if(map.get(a)>map.get(b))return 1;
        else if(map.get(b)>map.get(a))return -1;
        else{
            if(a>b)return -1;
            else if(a<b)return 1;
            return 0;
        }
    }
}
class Rextester
{  
    static Map<Integer,Integer>map;
    public static int[] frequencySort(int[] nums)
    {
        map=new HashMap<Integer,Integer>();
        for(int i:nums){
            if(map.containsKey(i)){
                map.put(i,1+map.get(i));
            }else{
                map.put(i,1);
            }
        }
        Integer[]arr=new Integer[nums.length];
        int k=0;
        for(int i:nums){
            arr[k++]=i;
        }
        Arrays.sort(arr,new Comp());
        k=0;
        for(int i:arr){
            nums[k++]=i;
        }
        return nums;
    }
    
    public static void main(String args[])
    {
        int[]nums={1,1,2,2,2,3};
        nums=frequencySort(nums);
        for(int i:nums)
        {
            System.out.print(i+" ");
        }
    }
}
1 3 3 2 2

ድግግሞሽ ሌትኮድ መፍትሄን በመጨመር ለድርድር ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (nlog (n)): የት n የግቤት ድርድር መጠን ነው። በሃሽ ካርታ ውስጥ ማስገባት እና መድረሻ ለ n አባሎች ኦ (n) ጊዜ ይወስዳል እና መደርደር ደግሞ የ nlogn ጊዜ ይወስዳል ፡፡ ስለዚህ የጊዜ ውስብስብነት nlogn ይሆናል።

የቦታ ውስብስብነት 

ኦ (n): በከፋ ሁኔታ በድርድሩ ውስጥ የተለያዩ አካላት ሊሆኑ ይችላሉ። ስለዚህ የካርታው መጠን ኦ (n) ይሆናል።