ફ્રીક્વન્સી લેટકોડ સોલ્યુશન વધારીને એરે સ Sર્ટ કરો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે ઇબે Twilio
અરે હેશમેપ સોર્ટિંગ

સમસ્યા નિવેદન

પૂર્ણાંકોની સંખ્યાના એરે આપેલ છે, મૂલ્યોની આવર્તનના આધારે એરેને વધતા ક્રમમાં સ sortર્ટ કરો. જો બહુવિધ મૂલ્યોમાં સમાન આવર્તન હોય, તો તેને ઘટતા ક્રમમાં સ sortર્ટ કરો.

ઉદાહરણ

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 હોય છે, તેથી તે ઘટતા ક્રમમાં ગોઠવાય છે.

અભિગમ

આ સમસ્યામાં સૌ પ્રથમ આપણે દરેક તત્વની આવર્તનની ગણતરી કરવી પડશે. આ માટે આપણે ઉપયોગ કરી શકીએ છીએ હેશ નકશો જાવા માં અથવા સી ++ માં અનોર્ડર્ડ સેટ. હવે આપણે ઇચ્છીએ છીએ કે આપણું પરિણામ એરે એ ઘટકોને પ્રથમ સમાવ્યું હોય જેમાં ઉચ્ચ આવર્તન હોય.
આ માટે આપણે આપેલ ઇનપુટ એરેને તેના કુલ આવર્તનના આધારે હવે સ sortર્ટ કરી શકીએ છીએ કે આપણે નકશામાં પહેલેથી જ સંગ્રહિત કરી છે.

હવે આપણે ફંક્શનની બહાર માત્ર એક કમ્પેરેટર બનાવવું પડશે. અહીં આપણે બે તત્વોની તુલના કરીશું (ચાલો a અને b કહીએ) અને આપણે દરેક તત્વની આવર્તન જાણીએ છીએ. તેથી જો a ની ફ્રીક્વન્સી b કરતા વધારે હોય તો એરે પહેલાં બી મુકો. આગળનો કેસ હશે જો a અને b ની આવર્તન સમાન હોય તો તે ઘટકને પહેલા મૂકો જેનું મૂલ્ય વધારે છે. ઉદાહરણ:

કેસ 1ફ્રીક્વન્સી લેટકોડ સોલ્યુશન વધારીને એરે સ Sર્ટ કરો

કેસ 2ફ્રીક્વન્સી લેટકોડ સોલ્યુશન વધારીને એરે સ Sર્ટ કરો

અલ્ગોરિધમ

  • હેશ નકશો બનાવો.
  • લૂપ ચલાવો અને દરેક તત્વ માટે 1 દ્વારા નકશામાં તે તત્વની સંખ્યા વધારવી.
  • હવે નકશામાં સંગ્રહિત તેની ગણતરીનો ઉપયોગ કરીને બે પૂર્ણાંકોની તુલના કરવા માટે તુલનાત્મક કાર્ય કરો. બે તત્વોની તુલના કરો અને ઉપર જણાવ્યા મુજબ તેમનો ઓર્ડર નક્કી કરો.
  • આ તુલનાત્મકનો ઉપયોગ કરીને આપેલ એરે સortર્ટ કરો.
  • સ theર્ટ થયેલ એરે પરત કરો.

અમલીકરણ

સી ++ પ્રોગ્રામ ફ્રીક્વન્સી લેટકોડ સોલ્યુશનમાં વધારો કરીને સ Sર્ટ એરે માટે

#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

ફ્રીક્વન્સી લેટકોડ સોલ્યુશન વધારીને સ Sર્ટ એરે માટે જાવા પ્રોગ્રામ

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

ફ્રીક્વન્સી લેટકોડ સોલ્યુશનમાં વધારો કરીને સ Sર્ટ એરે માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (નાલોગ (એન)): જ્યાં n એ ઇનપુટ એરેનું કદ છે. હેશ નકશામાં નિવેશ અને ક્સેસ એ એલિમેન્ટ્સ માટે ઓ (એન) સમય લે છે અને સ sortર્ટિંગમાં એનલોગનો સમય લાગે છે. તેથી સમય જટિલતા અવ્યવસ્થિત રહેશે.

અવકાશ જટિલતા 

ઓ (એન): ખરાબમાં તેઓ એરેમાં વિવિધ ઘટકો હોઈ શકે છે. આમ નકશાનું કદ O (n) હશે.