Жиіліктің жоғарылауы арқылы массивті сұрыптау Leetcode шешімі


Күрделілік дәрежесі оңай
Жиі кіреді еВау Twilio
Array HashMap Сұрыптау

Проблемалық мәлімдеме

Натурал сандар жиымы берілгенде, жиілікті мәндердің жиілігіне қарай өсу ретімен сұрыптаңыз. Егер бірнеше мәндердің жиілігі бірдей болса, оларды кему ретімен сұрыптаңыз.

мысал

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 ++ жүйесіндегі реттелмеген жиын. Енді біз нәтижелер массивінде алдымен жоғары жиіліктегі элементтердің болуын қалаймыз.
Ол үшін біз берілген жиым картада сақталған жиіліктің жалпы жиілігі бойынша сұрыптай аламыз.

Енді біз функциядан тыс компаратор жасауымыз керек. Мұнда біз екі элементті салыстырамыз (а және b делік) және біз әр элементтің жиілігін білеміз. Сонымен, егер a жиілігі b-ден үлкен болса, онда массивке b санын а-ға қойыңыз. Келесі жағдай, егер a мен b жиілігі бірдей болса, онда жоғары мәнге ие элементті бірінші орынға қойыңыз. Мысал:

Case 1Жиіліктің жоғарылауы арқылы массивті сұрыптау Leetcode шешімі

Case 2Жиіліктің жоғарылауы арқылы массивті сұрыптау Leetcode шешімі

Алгоритм

  • Хэш картасын жасаңыз.
  • Циклды іске қосыңыз және әрбір элемент үшін картадағы осы элементтің санын 1-ге көбейтіңіз.
  • Енді картада сақталған санды пайдаланып, екі бүтін санды салыстыруға арналған компаратор функциясын жасаңыз. Екі элементті салыстырып, олардың ретін жоғарыда талқылағандай шешіңіз.
  • Берілген жиымды осы компаратор көмегімен сұрыптаңыз.
  • Сұрыпталған жиымды қайтарыңыз.

Іске асыру

C ++ жиілігі Leetcode шешімін көбейту арқылы сұрыптау массивіне арналған бағдарлама

#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

Leetcode шешімінің жиілігін жоғарылату арқылы сұрыптау массивінің күрделілігін талдау

Уақыттың күрделілігі

O (nlog (n)): Мұндағы n - енгізу жиымының өлшемі. Хэш-картаға енгізу және кіру n элемент үшін O (n) уақытты алады, ал сұрыптау nlogn уақытты алады. Демек, уақыттың күрделілігі nlogn болады.

Ғарыштың күрделілігі 

O (n): Ең нашар жағдайда олар массивтегі n әр түрлі элементтер болуы мүмкін. Осылайша картаның өлшемі O (n) болады.