周波数Leetcodeソリューションを増やして配列を並べ替える


難易度 簡単に
よく聞かれる オークション Twilio
配列 ハッシュマップ 並べ替え(ソート)

問題文

整数numsの配列が与えられた場合、値の頻度に基づいて昇順で配列をソートします。 複数の値の頻度が同じである場合は、降順で並べ替えます。

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 ++の順序なしセット。 ここで、結果配列に、頻度の高い要素を最初に含める必要があります。
このために、マップにすでに保存されている合計頻度に基づいて、指定された入力配列を並べ替えることができます。

ここで、関数の外部にコンパレータを作成する必要があります。 ここでは、XNUMXつの要素(たとえばaとb)を比較し、各要素の頻度を確認します。 したがって、aの頻度がbより大きい場合は、配列内のaの前にbを置きます。 次のケースは、aとbの頻度が同じである場合、より高い値を持つ要素を最初に配置します。 例:

ケース1周波数Leetcodeソリューションを増やして配列を並べ替える

ケース2周波数Leetcodeソリューションを増やして配列を並べ替える

アルゴリズム

  • ハッシュマップを作成します。
  • ループを実行し、要素ごとに、マップ内のその要素の数を1ずつ増やします。
  • 次に、マップに格納されているカウントを使用してXNUMXつの整数を比較するためのコンパレータ関数を作成します。 XNUMXつの要素を比較し、上記のように順序を決定します。
  • このコンパレータを使用して、指定された配列をソートします。
  • ソートされた配列を返します。

製品の導入

周波数Leetcodeソリューションを増やすことによる配列のソートのための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

頻度Leetcodeソリューションを増やすことによる配列のソートのための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

周波数リートコードソリューションの増加によるソート配列の複雑さの分析

時間の複雑さ

O(nlog(n)): ここで、nは入力配列のサイズです。 ハッシュマップへの挿入とアクセスには、n個の要素に対してO(n)時間かかり、並べ替えにはnlogn時間かかります。 したがって、時間計算量は無視されます。

スペースの複雑さ 

オン) : 最悪の場合、それらは配列内のn個の異なる要素になる可能性があります。 したがって、マップのサイズはO(n)になります。