සංඛ්‍යාත ලීට්කෝඩ් විසඳුම වැඩි කිරීමෙන් අරා වර්ග කරන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඊ බේ ට්රිලිලියෝ
අරා හැෂ්මැප් වර්ග කිරීම

ගැටළු ප්රකාශය

නිඛිල සංඛ්‍යා සංඛ්‍යාවක් ලබා දී, අගයන්හි සංඛ්‍යාතය මත පදනම්ව අරාව වැඩි වන අනුපිළිවෙලට වර්ග කරන්න. බහු අගයන්ට එකම සංඛ්‍යාතයක් තිබේ නම්, ඒවා අඩු වන අනුපිළිවෙලට වර්ග කරන්න.

උදාහරණයක්

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 ක් ඇත, එබැවින් ඒවා අනුපිළිවෙල අනුව වර්ග කර ඇත.

ප්රවේශය

මෙම ගැටලුවේදී පළමුව අපි එක් එක් මූලද්රව්යයේ සංඛ්යාත ගණන් කළ යුතුය. මේ සඳහා අපට a භාවිතා කළ හැකිය හැෂ් සිතියම ජාවා හි හෝ ඇනවුම් නොකළ කට්ටලයක් c ++. දැන් අපට අවශ්‍ය වන්නේ අපගේ ප්‍රති result ල අරාව මුලින්ම ඉහළ සංඛ්‍යාතයක් සහිත මූලද්‍රව්‍ය අඩංගු වීමයි.
මේ සඳහා අපට ලබා දී ඇති ආදාන අරාව සිතියමෙහි අප දැනටමත් ගබඩා කර ඇති සම්පූර්ණ සංඛ්‍යාතය අනුව වර්ග කළ හැකිය.

දැන් අපි කළ යුත්තේ ශ්‍රිතයෙන් පිටත සංසන්දකයක් සෑදීමයි. මෙන්න අපි මූලද්රව්ය දෙකක් සංසන්දනය කරමු (a සහ b කියමු) සහ එක් එක් මූලද්රව්යයේ සංඛ්යාතය අපි දනිමු. එබැවින් a හි සංඛ්‍යාතය b ට වඩා වැඩි නම්, අරාවෙහි a ට පෙර b තබන්න. ඊළඟ අවස්ථාව වනුයේ a සහ b සංඛ්‍යාතය සමාන නම් වැඩි අගයක් ඇති එම මූලද්‍රව්‍යයට මුල් තැන දෙන්න. උදාහරණයක්:

නඩුව 1සංඛ්‍යාත ලීට්කෝඩ් විසඳුම වැඩි කිරීමෙන් අරා වර්ග කරන්න

නඩුව 2සංඛ්‍යාත ලීට්කෝඩ් විසඳුම වැඩි කිරීමෙන් අරා වර්ග කරන්න

ඇල්ගොරිතම

  • හැෂ් සිතියමක් සාදන්න.
  • ලූපයක් ධාවනය කරන්න, එක් එක් මූලද්‍රව්‍යය සඳහා සිතියමේ එම මූලද්‍රව්‍යයේ ගණන 1 කින් වැඩි කරන්න.
  • දැන් සිතියමේ ගබඩා කර ඇති ගණනය කිරීම් භාවිතා කරමින් පූර්ණ සංඛ්‍යා දෙකක් සංසන්දනය කිරීම සඳහා සංසන්දනාත්මක ශ්‍රිතයක් සාදන්න. මූලද්රව්ය දෙකක් සංසන්දනය කර ඉහත සාකච්ඡා කළ පරිදි ඒවායේ අනුපිළිවෙල තීරණය කරන්න.
  • මෙම සංසන්දකය භාවිතා කර දී ඇති අරාව වර්ග කරන්න.
  • වර්ග කළ අරාව නැවත ලබා දෙන්න.

ක්රියාත්මක කිරීම

සංඛ්‍යාත ලීට්කෝඩ් විසඳුම වැඩි කිරීමෙන් වර්ග කිරීම සඳහා සී ++ වැඩසටහන

#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

සංඛ්‍යාත ලීට්කෝඩ් විසඳුම වැඩි කිරීමෙන් වර්ග කිරීම සඳහා සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

O (nlog (n)): මෙහි n යනු ආදාන අරාවේ ප්‍රමාණයයි. හැෂ් සිතියම තුළට ඇතුළු කිරීම සහ ප්‍රවේශ වීම මූලද්‍රව්‍ය n සඳහා O (n) කාලයක් ගත වන අතර වර්ග කිරීම nlogn කාලය ගතවේ. එබැවින් කාල සංකීර්ණතාව nlogn වනු ඇත.

අභ්‍යවකාශ සංකීර්ණතාව 

මත) : නරකම දෙය නම් ඒවා අරාවෙහි විවිධ අංග n විය හැකිය. මේ අනුව සිතියමේ ප්‍රමාණය O (n) වේ.