फ़्रीक्वेंसी लेटेकोड सॉल्यूशन बढ़ाकर सॉर्ट करें


कठिनाई स्तर आसान
में अक्सर पूछा ईबे 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 की आवृत्ति होती है, इसलिए वे घटते क्रम में क्रमबद्ध हो जाते हैं।

दृष्टिकोण

इस समस्या में सबसे पहले हमें प्रत्येक तत्व की आवृत्तियों को गिनना होगा। इसके लिए हम एक का उपयोग कर सकते हैं हैश मैप जावा में या सी + + में unordered सेट। अब हम चाहते हैं कि हमारा परिणाम सरणी पहले उन तत्वों को समाहित करे जिसमें उच्च आवृत्ति हो।
इसके लिए हम दिए गए इनपुट ऐरे को अब उसकी कुल आवृत्ति के आधार पर सॉर्ट कर सकते हैं जिसे हमने पहले ही मैप में स्टोर कर लिया है।

अब हमें केवल फ़ंक्शन के बाहर एक तुलनित्र बनाना है। यहां हम दो तत्वों की तुलना करेंगे और (a और b कहते हैं) और हम प्रत्येक तत्व की आवृत्ति जानते हैं। इसलिए यदि a की आवृत्ति b से अधिक है तो सरणी में a से पहले b डालें। अगला मामला यह होगा कि यदि a और b की आवृत्ति समान है तो पहले उस तत्व को रखें जिसमें उच्च मान है। उदाहरण:

मामला 1फ़्रीक्वेंसी लेटेकोड सॉल्यूशन बढ़ाकर सॉर्ट करें

मामला 2फ़्रीक्वेंसी लेटेकोड सॉल्यूशन बढ़ाकर सॉर्ट करें

कलन विधि

  • एक हैश नक्शा बनाएँ।
  • एक लूप चलाएं और प्रत्येक तत्व के लिए 1 में उस तत्व की गिनती बढ़ाएँ।
  • अब मानचित्र में संग्रहीत इसकी गणना का उपयोग करके दो पूर्णांकों की तुलना करने के लिए एक तुलनित्र कार्य करें। दो तत्वों की तुलना करें और जैसा कि ऊपर चर्चा की गई है, उनका क्रम तय करें।
  • इस तुलनित्र का उपयोग करके दिए गए सरणी को क्रमबद्ध करें।
  • क्रमबद्ध सरणी लौटें।

कार्यान्वयन

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

आवृत्ति लेटेकोड सॉल्यूशन बढ़ाकर सॉर्ट एरे के लिए जटिलता विश्लेषण

समय जटिलता

O (nlog (n)): जहाँ n इनपुट सरणी का आकार है। हैश मानचित्र में सम्मिलन और पहुंच में n तत्वों के लिए O (n) समय लगता है और छांटने में nlogn समय लगता है। इसलिए समय की जटिलता को रोक दिया जाएगा।

अंतरिक्ष जटिलता 

पर) : सबसे कम उनके सरणी में अलग-अलग तत्व हो सकते हैं। इस प्रकार नक्शे का आकार O (n) होगा।