M අයිතම ඉවත් කිරීමෙන් පසු අවම මූලද්‍රව්‍ය ගණන


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ කළු ගල් ByteDance Expedia ඕලා කැබ්ස් ඔරකල් PayU SAP විද්‍යාගාර Yandex
අරා ගස

ගැටළු ප්රකාශය

“M අයිතම ඉවත් කිරීමෙන් පසු අවම මූලද්‍රව්‍ය ගණන” යන ගැටළුවෙහි දැක්වෙන්නේ ඔබට අ අරාව සහ පූර්ණ සංඛ්‍යාවක් 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 ක් ඇත, නමුත් මෙහි නඩුව වෙනස් වේ. අපට විවිධ සංඛ්‍යා 4 ක් තිබේ නම්, ඒවා සිදුවීම එක් එක් මූලද්‍රව්‍යයට එකකට වඩා වැඩි විය හැකිය. එවිට අපට එකම මූලද්‍රව්‍යය දෙවරක් හෝ සමහර විට වෙනස් මූලද්‍රව්‍ය දෙකක් ඉවත් කළ හැකිය, නමුත් m මූලද්‍රව්‍ය ඉවත් කිරීමෙන් පසුව ගණනය කළ හැකි පැහැදිලි මූලද්‍රව්‍යයන් අවම කළ යුතුය.

අපි පාවිච්චි කරන්නයි යන්නේ හැෂිං. අපි අ හෂ්මාප්. කැප් සහ ටෙම්ප් වල අගයන් 0 ලෙස සැකසීමෙන්, අපි අරාව හරහා ගමන් කිරීම ආරම්භ කර එක් එක් අරාව මූලද්‍රව්‍යයේ සංඛ්‍යාත සිතියමට ගණනය කර ගබඩා කරමු. මෙයට හේතුව එක් එක් මූලද්‍රව්‍යයේ සංඛ්‍යාතය අප දැනගත යුතු බැවිනි. නමුත්, අප පළමු වරට වටිනාකම ලබා ගන්නේ නම්, ගමන් කරන විට, අපි තොප්පියේ වටිනාකම 1 කින් වැඩි කරන්නෙමු, මූලික වශයෙන් එය අපට ධාරිතාවක් හෝ ප්‍රමාණයක් ලෙස ක්‍රියා කරයි.

අපි නැවත සිතියමක සෑම යතුරක්ම සහ අගයක්ම නැවත සලකා බලමු, මේ වතාවේ අපට සිතියමක ඕනෑම යතුරක් m ට වඩා කුඩා හෝ සමාන දැයි සොයා ගත යුතුය, ඉන්පසු ප්‍රධාන වේලාවන් අනුව m හි අගය අඩු කරන්න, අපි m ලෙස යාවත්කාලීන කළ යුතුය m - යතුර සොයාගෙන තාවකාලික වටිනාකම වැඩි කරන්න. මෙම තත්වය සෑහීමකට පත් නොවන්නේ නම්, අපට අවශ්‍ය වන්නේ තොප්පිය සහ තාවකාලිකත්වය අතර වෙනසයි. අන්තිමේදී, අපට එය ආපසු ලබා දිය යුතුයි cap-temp, සෑම කොන්දේසියක්ම කොටසකින් සෑහීමකට පත්වන්නේ නම් එය අවශ්‍ය ප්‍රතිදානය වන හෙයින්, අපට අතිරේක ප්‍රතිලාභ ප්‍රකාශයක් ඉදිරිපත් කළ යුතුය.

කේතය

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 අයිතම ඉවත් කිරීමෙන් පසු අවම මූලද්‍රව්‍ය ගණන සොයා ගැනීමට ජාවා කේතය

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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (එන් ලොග් එන්), කාල සංකීර්ණත්වය සඳහා ඉහළ සීමාව සලකුණු කරන වර්ග කිරීම අප භාවිතා කර ඇති බැවිනි.

අභ්‍යවකාශ සංකීර්ණතාව

මත), අපි එක් එක් මූලද්‍රව්‍යය යතුර ලෙස භාවිතා කළ නිසා. අපට N මූලද්‍රව්‍ය පාහේ තිබිය හැකිය.