ഫ്രീക്വൻസി ലീറ്റ്കോഡ് പരിഹാരം വർദ്ധിപ്പിച്ചുകൊണ്ട് അറേ അടുക്കുക  


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ബെ ട്വിలియో
അൽഗോരിതം അറേ കോഡിംഗ് ഹാഷ്‌മാപ്പ് അഭിമുഖം അഭിമുഖം ലീട്ട് കോഡ് LeetCodeSolutions ക്രമപ്പെടുത്തൽ

പ്രശ്നം പ്രസ്താവന  

ഒരു സംഖ്യ സംഖ്യകളുടെ ഒരു നിര നൽകിയാൽ, മൂല്യങ്ങളുടെ ആവൃത്തിയെ അടിസ്ഥാനമാക്കി ശ്രേണി ക്രമത്തിൽ അടുക്കുക. ഒന്നിലധികം മൂല്യങ്ങൾക്ക് ഒരേ ആവൃത്തി ഉണ്ടെങ്കിൽ, അവയെ ക്രമത്തിൽ അടുക്കുക.

ഉദാഹരണം

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 എന്ന് പറയാം) കൂടാതെ ഓരോ മൂലകത്തിന്റെയും ആവൃത്തി നമുക്കറിയാം. 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 ആയിരിക്കും.

ഇതും കാണുക
പദം ചേർത്ത് തിരയുക - ഡാറ്റ ഘടന രൂപകൽപ്പന ലീറ്റ്കോഡ്

ബഹിരാകാശ സങ്കീർണ്ണത 

O (n): ഏറ്റവും മോശം അവ അറേയിലെ വ്യത്യസ്ത ഘടകങ്ങളാകാം. അങ്ങനെ മാപ്പിന്റെ വലുപ്പം O (n) ആയിരിക്കും.

1