Мінімальная колькасць падмностваў з асобнымі элементамі


Узровень складанасці Лёгка
Часта пытаюцца ў Capital One GE Healthcare IBM Moonfrog Labs Яндэкс
масіў гашыш хэшавання сартаванне

Пастаноўка праблемы

Дапусцім, у вас ёсць масіў цэлых лікаў памерам 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.

Мінімальная колькасць падмностваў з асобнымі элементамі

Тлумачэнне

Мы далі цэлы масіў, у якім захоўваюцца дадатныя лікі. Мы папрасілі даведацца колькасць мінімальна магчымых падмностваў, якія можна сфармаваць з дадзенага масіва і якія маюць усе розныя элементы ў падмностве. Для гэтага мы будзем выкарыстоўваць Hashing, Hashing забяспечвае эфектыўнае рашэнне, пры якім мы можам дасягнуць складанасці ў часе замест наіўнага падыходу.

Мы збіраемся аб'явіць карту, падлічыць і захаваць частоты кожнага элемента масіва. Калі ў нас ёсць новы запіс на карце для нейкага элемента, мы робім для яго месца, і ў наступны раз пры ўзнікненні таго ж элемента мы проста атрымаем гэтае значэнне і павялічым яго частату на 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

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

 

Аналіз складанасці

Складанасць часу

Тут мы выкарысталі unordered_map або хэш-карту, якая робіць устаўку, выдаленне і абнаўленне ў O (1). Такім чынам, мы маем лінейную складанасць Аб (п) дзе "П" - колькасць элементаў у масіве.

Касмічная складанасць

Паколькі мы захоўваем пары ключоў і значэнняў, значыць, пры максімальнай колькасці будзе знойдзена n пар Аб (п) касмічная складанасць дзе "П" - колькасць элементаў у масіве. Такім чынам, можна сказаць, што алгарытм пошуку мінімальнай колькасці падмностваў з рознымі элементамі мае рашэнне лінейнай прасторавай складанасці.