빈도별로 요소 정렬


난이도 쉽게
자주 묻는 질문 아마존 신탁 조호 (Zoho) 자이쿠스
배열 해싱 정렬

문제 정책

당신은 주어진 정렬 정수의 일부 숫자가 반복됩니다. 문제 설명은 빈도별로 요소를 정렬하는 빈도에 따라 배열의 숫자를 내림차순으로 인쇄하도록 요청합니다.

arr[]={3,4,3,1,2,9,2,9,2,5 }
2 2 2 3 3 9 9 4 1 5

설명 : 여기에 인쇄 된 숫자는 빈도의 내림차순입니다. 숫자 2에는 최대 주파수가 있으므로 먼저 인쇄되고, 3과 9는 2와 동일한 주파수를 갖지만 3이 순서대로 먼저 인쇄되므로 9보다 먼저 인쇄되고 4, 1, 5는 주파수가 1입니다.

 

빈도별로 요소를 정렬하는 알고리즘

1. Declare a map.
2. Count and store the frequency of each number of an array into the map.
3. Select the keys with greater frequencies.
4. Get that frequency into val.
5. Print that key, its frequency number of times that is val.

설명

정수 배열을 제공했습니다. 우리는 주파수의 내림차순으로 배열을 인쇄하도록 요청했습니다. 배열에서 임의의 숫자가 최대 x 번 나오면 해당 숫자를 인쇄해야합니다. x x보다 작은 주파수를 가진 숫자가 순서대로 나옵니다. 이를 위해 해싱을 사용할 것입니다. 이를 위해지도를 사용할 것입니다.

우리는지도를 사용하고 배열을 횡단 할 것입니다. 그런 다음지도에 빈도와 함께 배열의 모든 숫자를 세고 저장합니다. 맵에 새로운 요소가 있으면 항목을위한 장소를 만드십시오. 그런 다음 주파수를 1로 표시합니다. 이미 존재하는 경우 주파수를 가져 와서 주파수를 1 씩 늘린 다음 동일한 숫자로 다시 누릅니다. 그런 다음 빈도에 따라 숫자를 정렬 할 때 결과 데이터를 저장할 데이터 구조를 취할 수 있습니다.

우리는지도를 횡단 할 것입니다. 그 후 주파수에 따라 배열을 정렬 할 것입니다. 감소하는 것은 더 높은 주파수를 가진 숫자가 먼저 나오고, 또한 원래 배열에서 나오는 것과 같이 정렬 된 배열에서 비슷한 빈도를 가진 숫자가 순서대로 온다는 것을 의미합니다. 각 키와 해당 값을 선택하고 해당 키를 인쇄합니다. 횟수. 직접 인쇄하지 않으려면 데이터 유형에 저장합니다. 여기서는 StringBuffer 또는 벡터를 사용하여 데이터를 저장하고 나중에 해당 데이터 유형 값을 인쇄 할 수 있습니다. 자동으로 정렬되어 최대 주파수를 확보하고 해당 주요 주파수를 인쇄합니다. 이것이 우리가 빈도별로 요소를 정렬하는 방법입니다.

빈도별로 요소 정렬

암호

빈도별로 요소를 정렬하는 C ++ 코드

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;
unordered_map<int, int> map1;
bool sortFrequency(const pair<int, int>& a, const pair<int, int>& b)
{
    if (a.second == b.second)
    {
        return map1[a.first] < map1[b.first];
    }
    return a.second > b.second;
}
void sortByFreq(int a[], int n)
{
    unordered_map<int, int> MAP;
    vector<pair<int, int> > vec;
    for (int i = 0; i < n; ++i)
    {
        MAP[a[i]]++;
        if (!map1.count(a[i]))
            map1[a[i]] = i + 1;
    }
    copy(MAP.begin(), MAP.end(), back_inserter(vec));
    sort(vec.begin(), vec.end(), sortFrequency);
    for (int i = 0; i < vec.size(); ++i)
        for (int j = 0; j < vec[i].second; ++j)
            cout << vec[i].first << " ";
}
int main()
{
    int arr[] = {3,4,3,1,2,9,2,9,2,5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    sortByFreq(arr, n);
    return 0;
}
2 2 2 3 3 9 9 4 1 5

 

빈도별로 요소를 정렬하는 Java 코드

import java.io.IOException;
import java.util.*;

class sortByFrequency
{
    public static StringBuffer sortFrequency(int arr1[], int l1)
    {
        Map<Integer, Integer> sortMap = frequencyMap(arr1, l1);
        StringBuffer output = new StringBuffer();

        sortMap.entrySet().stream()
        .sorted(Map.Entry.<Integer, Integer> comparingByValue().reversed())
        .forEach(e ->
        {
            int key = e.getKey();

            int val = e.getValue();

            for (int i = 0; i < val; i++)
            {
                output.append(key + " ");
            }
        });

        return output;
    }
    private static Map<Integer, Integer> frequencyMap(int[] arr, int l1)
    {
        Map<Integer, Integer> FrequencyMap = new LinkedHashMap<>();
        for (int i = 0; i < l1; i++)
        {
            if (FrequencyMap.containsKey(arr[i]))
            {
                FrequencyMap.put(arr[i], FrequencyMap.get(arr[i]) + 1);
            }
            else
            {
                FrequencyMap.put(arr[i], 1);
            }
        }
        return FrequencyMap;
    }
    public static void main(String[] args)
    {
        int arr[] = { 3,4,3,1,2,9,2,9,2,5 };
        System.out.println(sortFrequency(arr, arr.length));
    }
}
2 2 2 3 3 9 9 4 1 5

복잡성 분석

시간 복잡성

O (n + m 로그 m) 어디에 "엔" 배열의 총 요소 수이며 "엠" 배열에있는 고유 요소의 총 수입니다. mlogm은 m 개의 요소를 정렬 한 것입니다.

공간 복잡성

n 개의 요소를 저장하기 위해 맵과 배열을 사용했기 때문에 O (N) 어디에 "엔" 배열의 요소 수입니다.