Ар башка элементтери бар ички топтомдордун минималдуу саны


Кыйынчылык деңгээли жеңил
Көп суралган Capital One GE Саламаттыкты сактоо IBM Moonfrog Labs Яндекс
согуштук тизме таштанды Hashing сорттоо

Маселени билдирүү

Сизде ан бар дейли согуштук тизме 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

 

Java Code

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) ичине киргизүүнү, жок кылууну жана жаңыртууну камсыз кылган unordered_map же hash картасын колдондук. Ошентип, бизде сызыктуу татаалдык бар O (N) кайда "N" массивдеги элементтердин саны.

Космостун татаалдыгы

Биз ачкыч жана маани жуптарын сактап жаткандыктан, максимумда бизге n жуп болот O (N) космос татаалдыгы "N" массивдеги элементтердин саны. Ошентип, ар башка элементтери бар топтомдордун минималдуу санын табуунун алгоритмин айта алабыз, сызыктуу космостук татаалдык.