배열의 최고 주파수와 최소 주파수의 차이  


난이도 쉽게
자주 묻는 질문 포카이트 Roblox 테슬라
배열 해시 정렬

"배열의 최고 주파수와 최소 주파수 간의 차이"문제는 정수 정렬. 문제 설명은 배열에있는 두 개의 고유 숫자 중 가장 높은 빈도와 가장 낮은 빈도 사이의 최대 차이를 알아 내도록 요청합니다.

예  

배열의 최고 주파수와 최소 주파수의 차이

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

설명

주파수 1 → 3 (가장 높은 주파수)

주파수 5 → 1 (최저 주파수)

arr[] = {5, 4, 5, 5, 5, 3, 4 }
3

설명

주파수 5 → 4 (가장 높은 주파수)

주파수 3 → 1 (최저 주파수)

암호알고리즘  

  1. 선언 지도.
  2. 배열 요소의 빈도를 저장하고 계산합니다.
  3. 세트 최대 주파수 0 및 민프레크n.
  4. 지도 횡단 :
    1. 지도에서 maxfreq와 주파수 사이의 최대 값을 찾아서 maxfreq에 저장합니다.
    2. 지도에서 minfreq와 주파수 사이의 최소값을 찾아서 minfreq에 저장합니다.
  5. 반환 (maxfreq-minfreq).

설명

정수 배열이 있습니다. 우리의 임무는 배열에 존재하는 두 개의 고유 한 숫자의 가장 높은 발생과 가장 낮은 발생 사이의 최대 차이를 찾는 것입니다. 우리는 사용할 것입니다 해싱. 해싱은이 질문을 해결하는 효율적인 방법을 제공합니다. 우리는 맵을 선언하고 각 배열 요소의 주파수를 계산하고 동시에 요소와 함께 주파수를 맵에 저장합니다.

참조
합계가 0 인 모든 부분 배열 인쇄

그런 다음 값을 설정합니다. 최대 주파수 0 및 민프레크 즉, 주어진 배열의 크기보다 큰 주파수를 갖는 요소가 없기 때문에 배열의 길이. 우리는지도를 횡단하고 모든 요소를 ​​하나씩 집어 들고 주파수가 가장 큰지 또는 가장 낮은 지 확인합니다. 최대 주파수를 다른 변수로, 최소 주파수를 다른 변수로 분리하십시오. 최대 주파수와 최저 주파수의 차이를 반환해야하므로 (maxfreq-minfreq)를 반환합니다.

예를 들어 보겠습니다.

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

배열을 처음 탐색 할 때 요소와 발생 횟수를지도에 배치하고, 탐색 후지도를 다음과 같이 갖게됩니다.

지도 : {1 : 3, 2 : 2, 3 : 2, 5 : 1}

이제 맵에 각 요소의 발생이 있습니다. 맵을 가로 지르고 맵에서 각 요소를 선택하여 더 큰 현재 주파수 또는 maxfreq이고 최소 전류 주파수 또는 minfreq를 저장하고 각각 maxfreq 및 minfreq에 저장합니다.

  • 1 : 3 →

3은 maxfreq보다 크므로 maxfreq = 3

3은 minfreq보다 작으므로 minfreq = 3

  • 2 : 2 →

maxfreq가 2보다 크므로 maxfreq = 3

2은 minfreq보다 작으므로 minfreq = 2

  • 3 : 2 →

maxfreq가 2보다 크므로 maxfreq = 3

minfreq, minfreq = 2에서는 아무것도 변경되지 않습니다.

  • 5 : 1 →

maxfreq가 1보다 크므로 maxfreq = 3

1은 minfreq보다 작으므로 minfreq = 1

참조
그림 울타리 알고리즘

그리고 maxfreq-minfreq → (3-1) = 2의 차이를 반환합니다.

암호  

배열에서 가장 높은 빈도와 가장 낮은 빈도의 차이를 찾는 C ++ 코드

#include<iostream>
#include<unordered_map>

using namespace std;

int getMaximumDiff(int arr[], int n)
{
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;

    int maxfreq = 0, minfreq = n;
    for (auto x : freq)
    {
        maxfreq = max(maxfreq, x.second);
        minfreq = min(minfreq, x.second);
    }
    return (maxfreq - minfreq);
}
int main()
{
    int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumDiff(arr, n) << "\n";
    return 0;
}
2

배열에서 가장 높은 빈도와 가장 낮은 빈도의 차이를 찾기위한 Java 코드

import java.util.HashMap;
import java.util.Map;

class diffBWHighFLeastF
{
    public static int getMaximumDiff(int arr[], int n)
    {
        HashMap<Integer,Integer> freq = new HashMap<>();
        for (int i = 0 ; i < n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i], freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i], 1);
            }
        }
        int maxfreq = 0, minfreq = n;
        for (Map.Entry<Integer,Integer> x : freq.entrySet())
        {
            maxfreq = Math.max(maxfreq, x.getValue());
            minfreq = Math.min(minfreq, x.getValue());
        }
        return (maxfreq - minfreq);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
        int n = arr.length;
        System.out.println(getMaximumDiff(arr, n));
    }
}
2

복잡성 분석  

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 여기서 우리는 단순히 주파수를 추적하면서 배열의 요소를 순회했습니다. 이 모든 비용은 O (N) 시간입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 기껏해야 n 개의 요소가 모두 구별되는 경우 저장할 수 있습니다. 공간 복잡성은 선형입니다.