მკაფიო ელემენტების მინიმალური რაოდენობა მ ელემენტების ამოღების შემდეგ


Რთული ტური საშუალო
ხშირად ეკითხებიან BlackRock ByteDance Expedia ოლა კაბინები Oracle პეუ SAP ლაბორატორიები Yandex
Array ხე

პრობლემის განცხადება

პრობლემა "მკაფიო მკაფიო ელემენტების რაოდენობა m ამოღების შემდეგ" აცხადებს, რომ თქვენ გაქვთ მასივი და მთელი m. მასივის თითოეული ელემენტი მიუთითებს ნივთის ID- ს. პრობლემის დებულება ითხოვს m ელემენტების ამოღებას ისე, რომ მკაფიო ID– ს მინიმალური რაოდენობა უნდა დარჩეს.

მაგალითი

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

m=2
3

 

მკაფიო ელემენტების მინიმალური რაოდენობა მ ელემენტების ამოღების შემდეგ

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 რაოდენობის ელემენტებს ისე, რომ ამოღების შემდეგ. ამრიგად, უნდა გვქონდეს მკაფიო ელემენტის პირადობის მინიმალური რაოდენობა. დავუშვათ, რომ გვაქვს 4 რიცხვი, რომლებიც მკაფიო ელემენტებია და თუ ორს მოვიცილებთ. ჩვენ ჯერ კიდევ გვაქვს 2 განსხვავებული ელემენტი, მაგრამ საქმე აქ განსხვავებულია. თუ ჩვენ გვაქვს 4 განსხვავებული რიცხვი, მათი დაფიქსირება შეიძლება იყოს ერთზე მეტი თითოეული ელემენტისთვის. შემდეგ შეგვიძლია ერთი და იგივე ელემენტი ორჯერ ამოვიღოთ, ან შეიძლება ორი განსხვავებული ელემენტი, მაგრამ მ ელემენტების ამოღების შემდეგ მკაფიო ელემენტების რაოდენობა უნდა შევამციროთ.

ჩვენ ვაპირებთ გამოვიყენოთ ჰასინგი. ჩვენ გამოვაცხადებთ ა ჰაშმაპი. Cap და temp მნიშვნელობების 0-ზე დაყენება, ჩვენ დავიწყებთ მასივის გადახედვას და თითოეული მასივის ელემენტის სიხშირეების დათვლას და რუკაში შენახვას. ეს იმიტომ ხდება, რომ უნდა ვიცოდეთ თითოეული ელემენტის სიხშირე. ტრავმის დროს, თუ პირველად მივიღებთ მნიშვნელობას, 1-ით გავზრდით კაფის მნიშვნელობას, ძირითადად, ეს ჩვენთვის გამოდგება როგორც ტევადობა ან ზომა.

ჩვენ კვლავ მოვინახულებთ რუკის ყველა გასაღებას და მნიშვნელობებს, ამჯერად უბრალოდ უნდა ვიპოვნოთ, არის თუ არა რაიმე გასაღები რუკაზე ნაკლები, ან ტოლია m- ს, შემდეგ m- ს მნიშვნელობა შევამციროთ საკვანძო დროის მიხედვით, უნდა განაახლოთ m მ - გასაღები ნაპოვნია და გაზრდის ტემპის მნიშვნელობას. თუ ეს პირობა არ დააკმაყოფილა, ჩვენ უბრალოდ უნდა დავაბრუნოთ სხვაობა ქუდსა და ტემპერატურას შორის. ბოლოს და ბოლოს, ჩვენ უნდა დავუბრუნოთ cap-temp, რადგან ეს არის საჭირო გამოსავალი, თუ ყველა პირობა აკმაყოფილებს თუ ნაწილს, მაშინ ჩვენ უნდა დავდოთ დაბრუნების დამატებითი განაცხადი.

კოდი

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

სირთულის ანალიზი

დროის სირთულე

O (N log N), რადგან ჩვენ გამოვიყენეთ დახარისხება, რომელიც დროის სირთულის ზედა ზღვარს აღნიშნავს.

სივრცის სირთულე

O (N), რადგან თითოეული ელემენტი გამოვიყენეთ გასაღებად. შეიძლება გვქონდეს თითქმის N ელემენტები.