סאָרט עריי דורך ינקרעאַסינג אָפטקייַט לעעטקאָדע סאַלושאַן  


שוועריקייט לעוועל גרינג
אָפט געבעטן אין עבייַ טוויליאָ
אַלגערידאַמז מענגע קאָדירונג האַשמאַפּ אינטערוויו interviewprep LeetCode 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, אַזוי זיי זענען אויסגעשטעלט אין דיקריסינג סדר.

צוגאַנג  

אין דעם פּראָבלעם, מיר מוזן ציילן די אָפטקייַט פון יעדער עלעמענט. פֿאַר דעם מיר קענען נוצן אַ האַש מאַפּע אין Java אָדער אַנאָרדערד שטעלן אין C ++. איצט מיר וועלן אַז אונדזער רעזולטאַט מענגע כּולל די עלעמענט ערשטער מיט הויך אָפטקייַט.
פֿאַר דעם, מיר קענען סאָרט די געגעבן ינפּוט מענגע איצט אויף די יקער פון די גאַנץ אָפטקייַט וואָס מיר האָבן שוין סטאָרד אויף די מאַפּע.

איצט מיר נאָר מאַכן אַ קאָמפּאַראַטאָר אַרויס די פונקציע. דאָ מיר פאַרגלייכן צוויי עלעמענטן (לאָזן אונדז זאָגן a און b) און מיר וויסן די אָפטקייַט פון יעדער עלעמענט. אַזוי אויב אָפטקייַט פון a איז גרעסער ווי b, שטעלן b איידער a אין די מענגע. דער ווייַטער פאַל וועט זיין אויב אָפטקייַט פון a און b איז זעלביקער, שטעלן דעם עלעמענט ערשטער וואָס האָבן די העכער ווערט. בייַשפּיל:

זע אויך
דורכפירן סטרינג שיפץ לעעטקאָדע

פאַל קסנומקססאָרט עריי דורך ינקרעאַסינג אָפטקייַט לעעטקאָדע סאַלושאַןשפּילקע

פאַל קסנומקססאָרט עריי דורך ינקרעאַסינג אָפטקייַט לעעטקאָדע סאַלושאַןשפּילקע

אַלגאָריטהם

  • שאַפֿן אַ האַש מאַפּע.
  • לויפן אַ שלייף און פֿאַר יעדער עלעמענט ינקריסינג די ציילן פון דעם עלעמענט אין מאַפּע דורך 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

Java פּראָגראַם פֿאַר סאָרט עריי דורך ינקרעאַסינג לייזונג קאָד סאַלושאַן

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר סאָרט עריי דורך ינקריסינג אָפטקייַט לעעטקאָדע סאַלושאַן  

צייט קאַמפּלעקסיטי

אָ (nlog (n)): ווו n איז די גרייס פון דעם אַרייַנשרייַב מענגע. ינסערשאַן און אַקסעס אין האַש מאַפּע נעמט O (n) צייט פֿאַר n עלעמענטן און סאָרטינג נעמט Nlogn צייט. דערפאר די צייט קאַמפּלעקסיטי איז נלאָגן.

זע אויך
לייג און זוך וואָרט - דאַטן סטרוקטור פּלאַן לעעטקאָדע

ספעיס קאַמפּלעקסיטי 

אָ (n): אין ערגסט פון זיי, זיי קענען זיין אַנדערש עלעמענטן אין דער מענגע. אזוי די גרייס פון די מאַפּע וועט זיין O (n).

1