Минимум операција брисања да би сви елементи низа постали исти


Ниво тешкоће Лако
Често питани у адобе Фацтсет
Ред Хасх

Претпоставимо да имамо инпут од поредак са "Кс" број елемената. Задали смо проблем да морамо да пронађемо операције брисања, што би требало да буде минимум потребан за прављење једнаког низа, тј. Низ ће се састојати од једнаких елемената.

Пример

Улаз:

[1, 1, 4, 6, 2, 1]

Излаз:

3

objašnjenje:

Након уклањања (4, 6, 2) 3 елемента, низ постаје једнак, тј., [1, 1, 1]

Улаз:

[1, 5, 4, 16, 32, 9]

Излаз:

5

objašnjenje:

Можемо уклонити било који од 5 елемената како бисмо га учинили једнаким низом.

Алгоритам

  1. Спремите фреквенције свих елемената низа на мапу.
  2. Сет “Мак_фрек” до ИНТ_МИН.
  3. Пређите преко мапе и проверите који елемент има максималну учесталост.
    • Сет “Мак_фрек” до мак (мак_фрек, вредност) да би се пронашла максимална вредност међу свим фреквенцијама.
  4. Врати разлику између величине низа „Н“ мак_фрек (н - мак_фрек).

Објашњење

Дали смо проблем у којем морамо да сазнамо колико их је најмање брисање операције су потребне да би низ био једнак (сличних елемената). За ово ћемо користити мапу за чување фреквенције сваког броја који је присутан у низу.

Радећи ово, добићемо ону фреквенцију која је највећа међу свим фреквенцијама. Превлачењем по мапи можемо добити максималну учесталост коришћењем методе мак. Након понављања Мапа имаћемо максималну фреквенцију и треба да вратимо арраи_сизе - максималну фреквенцију, то значи да враћамо укупан број мањих фреквенција које се могу уклонити да би низ био једнак.

Размотримо пример:

дол: {10, 3, 4, 4, 2, 4};

  • и = 0, узима арр [и] као 10 и чува фрекв (10, 1).
  • и = 1, узима арр [и] као 3 и чува фрекв (3, 1).
  • за и = 2, арр [и] треба као 4 и чува фрекв (4, 1).
  • и = 3, потребно је арр [и] као 4, јер 4 већ има место на мапи, само додаје још један број на кључном месту 4 и чува фрекв (4, 2).
  • и = 4, узима арр [и] као 2 и чува фрекв (2, 1).
  • за и = 5, арр [и] треба као 4, пошто 4 већ има место на мапи, само додаје још један број на кључном месту 4 и чува фрекв (4, 3).

Између свега овога, једини број '4' има максималну фреквенцију која је 3, а након преласка и проналаска максималне фреквенције као 3 са мапе, вратићемо вредност (н - мак_фрек) 3. То је наш резултат.

Имплементација

Ц ++ програм за минималне операције брисања како би сви елементи низа били исти

#include <bits/stdc++.h>
using namespace std;

int minDelete(int arr[], int n)
{
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;

    int max_freq = INT_MIN;

    for (auto itr = freq.begin(); itr != freq.end(); itr++)
        max_freq = max(max_freq, itr->second);

    return n - max_freq;
}
int main()
{
    int arr[] = { 10, 3, 4, 4, 2, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minDelete(arr, n);
    return 0;
}
3

Јава програм за минималне операције брисања како би сви елементи низа били исти

import java.util.HashMap;
class minimumDeletionOperation
{
    public static int noOfMinimumDeletions(int arr[], int n)
    {
        HashMap<Integer,Integer> freq=new HashMap<Integer,Integer>();
        for(int i=0; i<arr.length; i++)
        {
            if(freq.containsKey(arr[i]))
                freq.put(arr[i], freq.get(arr[i]) + 1);
            else
                freq.put(arr[i], 1);
        }

        int max_freq=Integer.MIN_VALUE;

        for (int i:freq.keySet())
            max_freq = Math.max(max_freq, freq.get(i));

        return n - max_freq;
    }
    public static void main(String args[])
    {
        int arr[] = { 10, 3, 4, 4, 2, 4 };
        int n = arr.length;
        System.out.println(noOfMinimumDeletions(arr, n));
    }
}
3

Анализа сложености за минималне операције брисања како би сви елементи низа били исти

Сложеност времена

О (н) где „Н“ је број елемената у низу

Сложеност простора

О (н) где „Н“ је број елемената у низу