발생 빈도를 기준으로 요소 정렬


난이도 중급
자주 묻는 질문 아마존 신탁 조호 (Zoho) 자이쿠스
배열 해싱 해시맵

문제 정책

발생 빈도 문제로 요소를 정렬 할 때 정렬 ㅏ[]. 가장 많이 발생하는 요소가 먼저 오도록 배열 요소를 정렬합니다. 발생 횟수가 같으면 배열에서 처음 나타난 숫자를 인쇄합니다.

입력 형식

정수 값 N을 포함하는 첫 번째 줄.

N 개의 정수 값을 포함하는 두 번째 줄.

출력 형식

입력 배열 요소를 한 줄로 인쇄합니다. a [i]의 주파수가 a [i + 1]의 주파수보다 크거나 같은 방식입니다.

제약

  • 1 <= N <= 100000
  • -1e9 <= arr [i] <= 1e9

발생 빈도 별 정렬 요소 설명

질문에는 두 가지 주요 문제가 있습니다.

  • 빈도 및
  • 간섭 해결을위한 순서 유지.

우리는 두 가지 고급 및 강력한 데이터 구조를 사용합니다.

MAP  및  멀티맵.

맵에는 일부 키를 값에 매핑하는 속성이 있습니다. 멀티 맵은 동일한 기능을 수행하지만 맵 외에도 정렬 된 방식과 특정 순서로 키를 유지합니다. 정확히 우리가 요구하는 기능.

발생 빈도 별 정렬 요소 알고리즘

1.  지도에 요소 추가 (map ).
     a. 존재하지 않으면 추가하고 1로 만드십시오.
     b. 그렇지 않으면 값이 다시 발생할 때 값의 개수를 1 씩 증가시킵니다. 지도 제작 한 쌍.

2.  이제지도를 횡단하고 다음과 같이 멀티 맵에 요소를 계속 추가합니다.
     a. 맵의 두 번째 필드, 즉 맵의 빈도를 멀티 맵의 키로 만들어 자동으로 정렬되도록합니다.
     b. 멀티 맵의 각 항목이 유지되도록 첫 번째 값을 두 번째 값에 매핑합니다. 빈도에 따라 오름차순으로.

3. 이제 원하는 출력을 얻으려면 단순히 멀티 맵을 역순으로 횡단하십시오.

실시

발생 빈도 별 정렬 요소를위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
typedef multimap<int, int> MapType;
int main()
{
    int N;
    cin>>N;
    int a[N];
    for(int i=0;i<N;i++)
    {
       cin>>a[i];
    }
    //Map uses the first id as the array element and second as the count of occurrences of the element 
    map<int,int> mp; 
    for(int i=0;i<N;i++)
    {
        //if the array element is present then just increase the count of occurence of it by 1 
        if(mp.find(a[i])!=mp.end()){ 
            mp[a[i]]++;
        }
        else{
            //if the array element is not present in the map already then add it
            mp[a[i]]=1; 
        }
    }
    //it maintains specific order and count  and while inserting makes it sorted
    multimap<int,int> mp2; 
    map<int,int>::iterator it;
    for(it=mp.begin();it!=mp.end();it++){
      //Second becomes the key as we need to sort according to frequency.
      mp2.insert(MapType::value_type(it->second,it->first)); 
    }
    map<int,int>::reverse_iterator itr;
    for(itr=mp2.rbegin();itr!=mp2.rend();itr++)
    {
        //Reverse the multimap and print so that it prints in decreasing order.
        for(int i=0;i<itr->first;i++)
            cout<<itr->second<<"\t";
    }  
    return 0;
}

발생 빈도 별 정렬 요소를위한 Java 프로그램

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

class SortComparator implements Comparator<Integer> {
    private final Map<Integer, Integer> freqMap;
  
    // Assign the specified map
    SortComparator(Map<Integer, Integer> tFreqMap)
    {
        this.freqMap = tFreqMap;
    }
  
    // Compare the values
    @Override
    public int compare(Integer k1, Integer k2)
    {
  
        // Compare value by frequency
        int freqCompare = freqMap.get(k2).compareTo(freqMap.get(k1));
  
        // Compare value if frequency is equal
        int valueCompare = k1.compareTo(k2);
  
        // If frequency is equal, then just compare by value, otherwise -
        // compare by the frequency.
        if (freqCompare == 0)
            return valueCompare;
        else
            return freqCompare;
    }
}
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> outputArray = new ArrayList<>();
        for (int current : arr) 
        {
            int count = map.getOrDefault(current, 0);
            map.put(current, count + 1);
            outputArray.add(current);
        }
        // Compare the map by value
        SortComparator comp = new SortComparator(map);
        // Sort the map using Collections CLass
        Collections.sort(outputArray, comp);  
        // Final Output
        for (Integer i : outputArray) 
        {
            System.out.print(i + " ");
        }
    }
}
8
2 5 2 8 5 6 8 8
8 8 8 2 2 5 5 6

발생 빈도 별 정렬 요소에 대한 복잡성 분석

시간 복잡성

O (NlogN) 여기서 N은 배열에있는 요소의 수입니다. 여기에서는 정렬 된 멀티 맵에 요소를 정렬합니다.

공간 복잡성

O (N) 여기에서는 최대 크기가 N 인 멀티 맵과 맵을 사용하기 때문입니다.

참조