מספר מינימלי של אלמנטים נפרדים לאחר הסרת m פריטים


רמת קושי בינוני
נשאל לעתים קרובות בלקרוק Byte Expedia מוניות אולה אורקל PayU מעבדות SAP Yandex
מערך עֵץ

הצהרת בעיה

הבעיה "מספר מינימלי של אלמנטים נפרדים לאחר הסרת פריטים m" קובעת שיש לך מערך ומספר שלם מ '. כל רכיב במערך מציין מזהי פריט. הצהרת הבעיה מבקשת להסיר אלמנטים 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

הסבר

נותנים לנו מספר שלם מערך. יש לנו הצהרת בעיה שמסירה מספר מספר אלמנטים באופן שלאחר ההסרה. לכן, עלינו לקבל את המספר המינימלי של מזהי רכיבים מובחנים. נניח שיש לנו 4 מספרים שהם אלמנטים מובחנים ואם נסיר שניים מהם. עדיין יש לנו שני אלמנטים מובחנים, אך המקרה כאן שונה. אם יש לנו 2 מספרים שונים, המופע שלהם יכול להיות יותר מאחד עבור כל אלמנט. אז נוכל להסיר את אותו אלמנט פעמיים, או אולי שני אלמנטים שונים, אך עלינו למזער את ספירת האלמנטים המובהקים לאחר הסרת אלמנטים m.

אנחנו הולכים להשתמש has has. נכריז א מפת גיבוב. בהגדרת ערכי הכובע והטמפ 'ל -0, נתחיל לחצות את המערך ונמנה ונשמור את התדרים של כל אלמנט מערך במפה. הסיבה לכך היא שאנחנו צריכים לדעת את התדירות של כל אלמנט. אבל בעודנו עוברים אם נקבל את הערך בפעם הראשונה, נגדיל את ערך המכסה ב -1, בעצם זה עובד עבורנו כקיבולת או כגודל.

נבקר שוב בכל מפתח וערכים של מפה, הפעם עלינו רק למצוא אם מפתח כלשהו במפה קטן או שווה ל- m, ואז להקטין את הערך של m לפי זמני מפתח, עלינו לעדכן את m כ m - מפתח נמצא ולהגדיל את ערך הטמפ '. אם תנאי זה אינו מקיים, עלינו רק להחזיר את ההפרש בין מכסה לטמפ '. סוף סוף, עלינו להחזיר את ה- temp-tempמכיוון שזו התפוקה הנדרשת אם כל תנאי עומד בחלק אם חלק, עלינו לשים הצהרה נוספת על החזר.

קופונים

קוד C ++ לאיתור מספר מינימלי של אלמנטים נפרדים לאחר הסרת פריטים m

#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

קוד Java כדי למצוא מספר מינימלי של אלמנטים נפרדים לאחר הסרת פריטים m

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 יומן N), כי השתמשנו במיון המסמן את הגבול העליון למורכבות הזמן.

מורכבות בחלל

O (N) כי השתמשנו בכל אלמנט כמפתח. יכולים להיות לנו כמעט אלמנטים N.