Шумораи ҳадди ақали зергурӯҳҳо бо унсурҳои гуногун


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Пойтахт Яке аз GE Тандурустӣ IBM Озмоишгоҳҳои Moonfrog Yandex
тартиботи ҳарбӣ Хаш Хашм Sorting

Изҳороти мушкилот

Фарз мекунем, ки шумо як асал ададҳои андозаи 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 ё hash -ро истифода кардем, ки дохилкунӣ, ҳазф ва навсозиро дар O (1) месозад. Ҳамин тариқ, мо як мураккабии хаттии Эй (н) ки дар "Н" шумораи унсурҳои массив аст.

Мураккабии фазо

Азбаски мо ҷуфтҳои калидӣ ва қиматро нигоҳ медорем, пас дар ҳадди аксар, n ҷуфт вуҷуд хоҳад дошт, ки ба мо медиҳад Эй (н) мураккабии фазо дар куҷо "Н" шумораи унсурҳои массив аст. Ҳамин тариқ, мо метавонем алгоритми ёфтани миқдори минимуми зерҷузъҳоро бо унсурҳои гуногун ҳалли мураккабии фазоии хаттӣ гӯем.