Ταξινόμηση συστοιχίας με αύξηση της συχνότητας Leetcode Solution


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις eBay Twilio
Παράταξη 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 ++. Τώρα θέλουμε ο πίνακας αποτελεσμάτων να περιέχει πρώτα εκείνα τα στοιχεία που έχουν υψηλή συχνότητα.
Γι 'αυτό μπορούμε να ταξινομήσουμε τον δεδομένο πίνακα εισαγωγής τώρα με βάση τη συνολική του συχνότητα που έχουμε ήδη αποθηκεύσει στον χάρτη.

Τώρα πρέπει απλώς να κάνουμε ένα συγκριτικό εκτός της συνάρτησης. Εδώ θα συγκρίνουμε δύο στοιχεία (ας πούμε α και β) και γνωρίζουμε τη συχνότητα κάθε στοιχείου. Έτσι, εάν η συχνότητα του a είναι μεγαλύτερη από το b, βάλτε το b πριν από το a στο πίνακα. Η επόμενη περίπτωση θα είναι εάν η συχνότητα των a και b είναι ίδια, τότε βάλτε πρώτα το στοιχείο που έχει την υψηλότερη τιμή. Παράδειγμα:

Υπόθεση 1Ταξινόμηση συστοιχίας με αύξηση της συχνότητας Leetcode Solution

Υπόθεση 2Ταξινόμηση συστοιχίας με αύξηση της συχνότητας Leetcode Solution

Αλγόριθμος

  • Δημιουργήστε έναν κατακερματισμό χάρτη.
  • Εκτελέστε ένα βρόχο και για κάθε στοιχείο αυξάνεται ο αριθμός του στοιχείου στο χάρτη κατά 1.
  • Τώρα κάντε μια λειτουργία σύγκρισης για τη σύγκριση δύο ακέραιων αριθμών χρησιμοποιώντας τον αριθμό του που είναι αποθηκευμένος στο χάρτη. Συγκρίνετε δύο στοιχεία και αποφασίστε τη σειρά τους όπως συζητήθηκε παραπάνω.
  • Ταξινόμηση του δεδομένου πίνακα χρησιμοποιώντας αυτό το συγκριτικό.
  • Επιστρέψτε τον ταξινομημένο πίνακα.

Εκτέλεση

Πρόγραμμα C ++ για ταξινόμηση σειράς με αύξηση της συχνότητας Leetcode Solution

#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 για ταξινόμηση σειράς με αύξηση της συχνότητας Leetcode Solution

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 Solution

Χρόνος πολυπλοκότητας

O (nlog (n)): όπου n είναι το μέγεθος του πίνακα εισαγωγής. Η εισαγωγή και η πρόσβαση στο χάρτη κατακερματισμού απαιτεί χρόνο O (n) για στοιχεία n και η ταξινόμηση απαιτεί χρόνο nlogn. Ως εκ τούτου, η πολυπλοκότητα του χρόνου θα είναι μηδενική.

Διαστημική πολυπλοκότητα 

Επί) : Στη χειρότερη περίπτωση μπορούν να είναι διαφορετικά στοιχεία στον πίνακα. Έτσι το μέγεθος του χάρτη θα είναι O (n).