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

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

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

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

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

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 및 민프레크 즉, 주어진 배열의 크기보다 큰 주파수를 갖는 요소가 없기 때문에 배열의 길이. 우리는지도를 횡단하고 모든 요소를 ​​하나씩 집어 들고 주파수가 가장 큰지 또는 가장 낮은 지 확인합니다. 최대 주파수를 다른 변수로, 최소 주파수를 다른 변수로 분리하십시오. 최대 주파수와 최저 주파수의 차이를 반환해야하므로 (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 개의 요소가 모두 구별되는 경우 저장할 수 있습니다. 공간 복잡성은 선형입니다.

균열 시스템 설계 인터뷰
Translate »