Массивди жыштыкты көбөйтүү менен чечүү Leetcode Solution


Кыйынчылык деңгээли жеңил
Көп суралган Окшош Twilio
согуштук тизме HashMap сорттоо

Маселени билдирүү

Сан сандарынан турган массив берилгендиктен, массивди маанилеринин жыштыгына жараша өсүп жаткан ирети менен иреттеңиз. Эгерде бир нече маани бирдей жыштыкка ээ болсо, аларды азайуу ирети менен иреттеңиз.

мисал

nums = [1,1,2,2,2,3]
[3,1,1,2,2,2]

Explanation:

'3' - 1, '1' - 2, '2' - 3.

nums = [2,3,1,3,2]
[1,3,3,2,2]

Explanation:

'2' жана '3' экөө тең 2дин жыштыгына ээ, андыктан алар азайуу ирети менен сорттолгон.

жакындоо

Бул маселеде биринчиден, биз ар бир элементтин жыштыгын эсептешибиз керек. Бул үчүн биз колдоно алабыз таштанды карта java же c ++ тилкесинде иретке салынбаган. Эми биздин натыйжалар массивибиз биринчи кезекте жогорку жыштыктагы элементтерди камтышы керек.
Ал үчүн биз берилген массивди картада мурунтан сакталып калган жалпы жыштыгынын негизинде иреттей алабыз.

Эми функциясынан тышкары компаратор жасаш керек. Бул жерде биз эки элементти салыштырабыз (а жана б деп айтайык) жана ар бир элементтин жыштыгын билебиз. Демек, а-нын жыштыгы bдан чоң болсо, анда bди массивге а-нын алдына коюңуз. Кийинки абал, эгерде a жана b жыштыгы бирдей болсо, анда жогору турган элементти биринчи орунга коюңуз. Мисалы:

Case 1Массивди жыштыкты көбөйтүү менен чечүү Leetcode Solution

Case 2Массивди жыштыкты көбөйтүү менен чечүү Leetcode Solution

Algorithm

  • Хэш картасын түзүү.
  • Циклди иштетип, ар бир элемент үчүн картадагы элементтин санын 1ге көбөйтүңүз.
  • Эми картада сакталган эсептөөнү колдонуп, эки бүтүн санды салыштыруу үчүн компаратор функциясын жасаңыз. Эки элементти салыштырып, алардын тартибин жогоруда талкуулангандай чечиңиз.
  • Берилген массивди ушул компаратордун жардамы менен иреттеңиз.
  • Сорттолгон массивди кайтарыңыз.

ишке ашыруу

C ++ программасы Freetency 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 Frequency 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

Freetency Leetcode Чечимин жогорулатуу менен Сорттоо массивинин татаалдыгын талдоо

Убакыт татаалдыгы

O (nlog (n)): мында n - киргизүү массивинин көлөмү. Хэш картага киргизүү жана кирүү n элемент үчүн O (n) убакытты, ал эми сорттоо nlogn убакытты талап кылат. Демек, убакыттын татаалдыгы nlogn болот.

Космостун татаалдыгы 

O (n): Жаман учурларда, алар массивдеги n башка элементтер болушу мүмкүн. Ошентип, картанын көлөмү O (n) болот.