주파수 Leetcode 솔루션을 증가시켜 배열 정렬  


난이도 쉽게
자주 묻는 질문 이베이 Twilio
알고리즘 배열 코딩 해시맵 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 정렬

문제 정책  

정수 숫자 배열이 주어지면 값의 빈도에 따라 오름차순으로 배열을 정렬합니다. 여러 값의 빈도가 동일한 경우 내림차순으로 정렬합니다.

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)를 비교하고 각 요소의 빈도를 알고 있습니다. 따라서 a의 주파수가 b보다 크면 배열에서 a 앞에 b를 넣으십시오. 다음 경우는 a와 b의 주파수가 같으면 더 높은 값을 가진 요소를 먼저 배치하는 것입니다. 예:

참조
문자열 이동 Leetcode 수행

사례 주파수 Leetcode 솔루션을 증가시켜 배열 정렬

사례 주파수 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

주파수를 증가시켜 배열 정렬을위한 자바 프로그램 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입니다.

참조
단어 추가 및 검색-데이터 구조 설계 LeetCode

공간 복잡성 

의 위에) : 최악의 경우 배열에서 n 개의 다른 요소가 될 수 있습니다. 따라서 맵의 크기는 O (n)이됩니다.

1