Массивро ҷобаҷогузорӣ кунед бо роҳи зиёд кардани ҳалли Leetcode басомади


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад мехаранд Тиллио
тартиботи ҳарбӣ HashMap Sorting

Изҳороти мушкилот

Бо назардошти массиви ададҳои адад, массивро бо тартиби афзоиш дар асоси басомади арзишҳо ҷудо кунед. Агар қиматҳои сершумор басомади якхела дошта бошанд, онҳоро бо тартиби камшавӣ ҷудо кунед.

мисол

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 калонтар бошад, пас дар массив bро пеш аз a гузоред. Ҳолати навбатӣ хоҳад буд, агар басомади а ва b якхела бошад, пас он унсурро, ки арзиши баландтар доранд, аввал гузоред. Мисол:

Парвандаи 1Массивро ҷобаҷогузорӣ кунед бо роҳи зиёд кардани ҳалли Leetcode басомади

Парвандаи 2Массивро ҷобаҷогузорӣ кунед бо роҳи зиёд кардани ҳалли Leetcode басомади

Алгоритм

  • Харитаи хэш созед.
  • Доираро иҷро кунед ва барои ҳар як элемент ҳисоби ин элементро дар харита 1 зиёд кунед.
  • Акнун функсияи компараторро барои муқоисаи ду адад бо истифода аз ҳисоби он дар харита ҳифз кунед. Ду унсурро муқоиса кунед ва тартиби онҳоро тавре, ки дар боло муҳокима карда шуд, ҳал кунед.
  • Масви додашударо бо ёрии ин компаратор ҷудо кунед.
  • Массиви ҷудошударо баргардонед.

татбиќи

Барномаи C ++ барои Array Sort тавассути зиёд кардани ҳалли 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 барои Array Sort тавассути зиёд кардани ҳалли Leetcode басомади

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) мешавад.