m 개 항목을 제거한 후 고유 요소의 최소 수

난이도 중급
자주 묻는 질문 BlackRock ByteDance Expedia 올라 택시 신탁 알레그로 SAP 연구소 Yandex 주차
배열 나무조회수 35

문제 정책

"m 개 항목을 제거한 후 고유 요소의 최소 수"문제는 정렬 및 정수 m. 배열의 각 요소는 항목 ID를 나타냅니다. 문제 설명은 최소한의 고유 ID가 남아 있어야하는 방식으로 m 개의 요소를 제거하도록 요청합니다.

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

m=2
3

 

m 개 항목을 제거한 후 고유 요소의 최소 수

arr[] = {1, 4, 4, 1}

m=2
2

m 개 항목을 제거한 후 고유 요소의 최소 수를 찾는 알고리즘

1. Declare a map.
2. Set temp to 0.
3. Count and store the frequencies of each element of the array into the map and check how many unique keys are present in it and set it as a cap.
4. Traverse the map and check if the key element is less than or equal to m.
    1. If true then decrease the value of m up to that key and also increase the temp by 1.
    2. Else return cap-temp.
5. Return cap-temp

설명

정수가 주어집니다 정렬. 제거 후 m 개의 요소를 제거하는 문제 진술이 있습니다. 따라서 우리는 최소한의 고유 한 요소 ID를 가져야합니다. 별개의 요소 인 4 개의 숫자가 있고 그중 2 개를 제거한다고 가정합니다. 우리는 여전히 4 개의 별개의 요소를 가지고 있지만 여기의 경우는 다릅니다. XNUMX 개의 다른 숫자가있는 경우 각 요소에 대해 하나 이상의 숫자가 발생할 수 있습니다. 그런 다음 동일한 요소를 두 번 제거하거나 두 개의 다른 요소를 제거 할 수 있지만 m 요소를 제거한 후 고유 요소 수를 최소화해야합니다.

우리는 사용할 것입니다 해싱. 우리는 해시 맵. cap과 temp의 값을 0으로 설정하면 배열을 탐색하고 각 배열 요소의 빈도를 계산하여 맵에 저장합니다. 각 요소의 빈도를 알아야하기 때문입니다. 그러나 처음으로 값을 얻으면 순회하는 동안 cap의 값을 1 씩 늘릴 것입니다. 기본적으로 용량 또는 크기로 작동합니다.

지도의 모든 키와 값을 다시 방문합니다. 이번에는지도의 키가 m보다 작거나 같은지 확인한 다음 m 값을 키 시간만큼 줄이면 m을 다음과 같이 업데이트해야합니다. m – 키 온도의 값을 찾고 증가시킵니다. 이 조건이 충족되지 않으면 캡과 온도의 차이를 반환하면됩니다. 마지막으로 우리는 모자 온도, 모든 조건이 if 부분을 충족하는 경우 필요한 출력이므로 추가 반환 진술을 입력해야합니다.

암호

m 항목을 제거한 후 고유 요소의 최소 수를 찾는 C ++ 코드

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>

using namespace std;

int getMinimumDistinctIds(int arr[], int n, int m)
{
    unordered_map<int, int> MAP;
    vector<pair<int, int> > vec;
    int temp = 0;

    for (int i = 0; i < n; i++)
        MAP[arr[i]]++;

    for (auto it = MAP.begin(); it != MAP.end(); it++)
        vec.push_back(make_pair(it->second, it->first));

    sort(vec.begin(), vec.end());

    int cap = vec.size();

    for (int i = 0; i < cap; i++)
    {
        if (vec[i].first <= m)
        {
            m = m - vec[i].first;
            temp++;
        }
        else
            return cap - temp;
    }
    return cap - temp;
}
int main()
{
    int arr[] = { 1, 3, 4, 2, 4, 1, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 2;
    cout << getMinimumDistinctIds(arr, n, m);
    return 0;
}
3

m 항목을 제거한 후 고유 요소의 최소 수를 찾는 Java 코드

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


class MinimumDistinctId
{
    public static int getMinimumDistinctIds(int arr[], int n, int m)
    {
        Map<Integer, Integer> MAP = new HashMap<Integer, Integer>();
        int temp = 0;
        int cap = 0;
        for (int i = 0; i < n; i++)
        {
            if (MAP.containsKey(arr[i]) == false)
            {
                MAP.put(arr[i], 1);
                cap++;
            }
            else
                MAP.put(arr[i], MAP.get(arr[i]) + 1);
        }
        for (Entry<Integer, Integer> entry:MAP.entrySet())
        {
            if (entry.getKey() <= m)
            {
                m = m - entry.getKey();
                temp++;
            }
            else
                return cap - temp;
        }
        return cap - temp;
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 3, 4, 2, 4, 1, 3};
        int m = 2;
        System.out.println(getMinimumDistinctIds(arr, arr.length, m));
    }
}
3

복잡성 분석

시간 복잡성

O (N log N), 시간 복잡성의 상한선을 표시하는 정렬을 사용했기 때문입니다.

공간 복잡성

의 위에), 각 요소를 키로 사용했기 때문입니다. 거의 N 개의 요소를 가질 수 있습니다.

Translate »