ಆವರ್ತನ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಹೆಚ್ಚಿಸುವ ಮೂಲಕ ಅರೇ ಅನ್ನು ವಿಂಗಡಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಇಬೇ ಟ್ವಿಲಿಯೊ
ಅರೇ ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್ ವಿಂಗಡಿಸಲಾಗುತ್ತಿದೆ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ಪೂರ್ಣಾಂಕಗಳ ಸಂಖ್ಯೆಗಳ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನೀಡಿದರೆ, ಮೌಲ್ಯಗಳ ಆವರ್ತನದ ಆಧಾರದ ಮೇಲೆ ಶ್ರೇಣಿಯನ್ನು ಹೆಚ್ಚಿಸುವ ಕ್ರಮದಲ್ಲಿ ವಿಂಗಡಿಸಿ. ಬಹು ಮೌಲ್ಯಗಳು ಒಂದೇ ತರಂಗಾಂತರವನ್ನು ಹೊಂದಿದ್ದರೆ, ಅವುಗಳನ್ನು ಕಡಿಮೆಗೊಳಿಸುವ ಕ್ರಮದಲ್ಲಿ ವಿಂಗಡಿಸಿ.

ಉದಾಹರಣೆ

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 ನ ಆವರ್ತನವು 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) ಆಗಿರುತ್ತದೆ.