फ्रिक्वेन्सी लेटकोड सोल्यूशन वाढवून अ‍ॅरेची क्रमवारी लावा


अडचण पातळी सोपे
वारंवार विचारले हा कोड eBay Twilio
अरे हॅशमॅप वर्गीकरण

समस्या विधान

पूर्णांक संख्यांचा अ‍ॅरे दिल्यास मूल्यांच्या वारंवारतेवर आधारित अ‍ॅरे वाढत्या क्रमवारीत क्रमवारीत लावा. एकाधिक मूल्यांमध्ये समान वारंवारता असल्यास, त्यास घटत्या क्रमाने क्रमवारीत लावा.

उदाहरण

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 वापरू शकतो हॅश नकाशा जावा मध्ये किंवा सी ++ मध्ये अनअर्डर सेट. आता आमच्या निकालाच्या अ‍ॅरेमध्ये प्रथम घटक असणे आवश्यक आहे ज्यात उच्च वारंवारता आहे.
यासाठी आम्ही दिलेल्या इनपुट अ‍ॅरेची आतापर्यंत आम्ही नकाशात आधीच संग्रहित केलेल्या एकूण वारंवारतेच्या आधारावर क्रमवारी लावू शकतो.

आता फंक्शनच्या बाहेर फक्त एक कंपॅरटर बनवावा लागेल. येथे आपण दोन घटकांची तुलना करणार आहोत (अ आणि बी समजा) आणि आम्हाला प्रत्येक घटकाची वारंवारता माहित आहे. तर 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

फ्रिक्वेन्सी लेटकोड सोल्यूशन वाढवून क्रमवारीसाठी अ‍ॅरेसाठी कॉम्प्लेक्सिटी विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (नलॉग (एन)): जेथे एन इनपुट अ‍ॅरेचा आकार आहे. हॅश नकाशामध्ये समाविष्ट करणे आणि प्रवेशासाठी एन घटकांना ओ (एन) वेळ लागतो आणि क्रमवारी लावण्यास नळ लागतो. म्हणून वेळेची गुंतागुंत कोंडी होईल.

स्पेस कॉम्प्लेक्सिटी 

ओ (एन): सर्वात वाईट म्हणजे अ‍ॅरेमधील ते भिन्न घटक असू शकतात. अशा प्रकारे नकाशाचा आकार ओ (एन) असेल.