고유 한 요소가있는 하위 집합의 최소 수

난이도 쉽게
자주 묻는 질문 자본 하나 GE 헬스 케어 IBM 문 프로그 연구소 Yandex 주차
배열 해시 해싱 정렬조회수 52

문제 정책

당신이 정렬 크기 n의 정수. 문제 설명은 고유 한 요소가있는 하위 집합의 최소 수를 알아 내도록 요청합니다. 즉, 배열에서 다른 / 고유 한 요소를 모두 포함하여 형성 할 수있는 하위 집합입니다.

arr[] = {2,4,6,2,1,4,2}
3

설명 : {1, 2, 4, 6}, {2, 4} 및 {2}는 서브 세트가 될 수 있습니다.

arr[] = {2,5,6,7,5,4,2}
3

설명 : {2, 5, 6, 7} 및 {2, 4}는 두 개의 서브 세트가 될 수 있습니다.

 

고유 한 요소가있는 하위 집합의 최소 수를 찾는 알고리즘

1. Declare a map and count and store the frequency of each element of the array into the map.
2. Set output to 0.
3. Traverse the map and find out the maximum between the output and each value of key in the map and store it into the output.
4. Return the value of output.

고유 한 요소가있는 하위 집합의 최소 수

설명

우리는 양수가 저장되는 정수 배열을 제공했습니다. 주어진 배열에서 형성 될 수 있고 하위 집합에 모든 고유 요소를 포함하는 가능한 최소 하위 집합의 수를 알아 내도록 요청했습니다. 이를 위해 해싱을 사용할 것입니다. 해싱은 순진한 접근 방식 대신 적절한 시간 복잡성을 달성 할 수있는 효율적인 솔루션을 제공합니다.

맵을 선언하고, 배열의 각 요소에 대한 빈도를 계산하고 저장합니다. 일부 요소에 대한 맵에 새 항목이있는 경우 해당 요소에 대한 위치를 만들고 다음 번에 동일한 요소가 발생하면 해당 값을 가져 와서 빈도를 1 씩 증가시킵니다. C ++에서 자체적으로 요소를 선택합니다. 그런 다음 증가 연산을 수행하지만 Java에서는 특히 해당 요소를 확인합니다. 우리는 모든 요소 중에서 최대 주파수를 찾아 답을 얻을 것이기 때문에 주파수 수를 저장하고 있습니다.

출력을 0으로 설정 한 다음 각 요소의 빈도를 저장 한지도를 탐색합니다. 이것으로 우리는 배열을 정렬 할 필요가 없습니다.지도를 사용하면 이미 정렬 된 요소가 있기 때문입니다. 각 요소를 선택하고 해당 주파수를 가져와 출력과 비교합니다. 이 두 값의 최대 값, 출력 및 선택한 요소의 빈도를 알아 내야합니다. 그리고 그것은 별개의 요소가있는 최소 하위 집합 수를 찾는 데 필요한 답입니다.

고유 한 요소가있는 하위 집합의 최소 수를 찾는 코드

C ++ 코드

#include <iostream>
#include<unordered_map>

using namespace std;

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

    int output = 0;
    for (auto x : mp)
        output = max(output, x.second);

    return output;
}
int main()
{
    int arr[] = {2,4,6,2,1,4,2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMinSubset(arr, n);
    return 0;
}
3

 

자바 코드

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

class MinimumSubsets
{
    public static int getMinSubset(int arr[], int n)
    {
        HashMap<Integer, Integer> mp = new HashMap<>();
        for (int i = 0; i < n; i++)
            mp.put(arr[i],mp.get(arr[i]) == null?1:mp.get(arr[i])+1);

        int output = 0;
        for (Map.Entry<Integer,Integer> entry : mp.entrySet())
            output = Math.max(output, entry.getValue());

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 2,4,6,2,1,4,2};
        int n = arr.length;
        System.out.println( getMinSubset(arr, n));

    }
}
3

 

복잡성 분석

시간 복잡성

여기에서는 O (1)에서 삽입, 삭제 및 업데이트를 수행하는 무순 맵 또는 해시 맵을 사용했습니다. 따라서 우리는 다음과 같은 선형 복잡성을가집니다. O (N) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

키와 값 쌍을 저장하고 있으므로 최대 값에는 n 개의 쌍이 있습니다. O (N) 공간 복잡성 "엔" 배열의 요소 수입니다. 따라서 고유 한 요소가있는 하위 집합의 최소 수를 찾는 알고리즘은 선형 공간 복잡도 솔루션을 가지고 있다고 말할 수 있습니다.

Translate »