Барлық элементтерді массивке тең ету үшін минималды жұмыс


Күрделілік дәрежесі оңай
Жиі кіреді Amazon BlackRock Цитадель Directi Flipkart шынында Яндекс
Array Хэш

«Барлық элементтерді массивке тең етудің минималды жұмысы» есебінде сізге берілгені айтылады массив кейбіреулерімен бүтін сандар ішінде. Массивті теңестіру үшін жасалатын минималды амалдарды білу керек.

мысал

Барлық элементтерді массивке тең ету үшін минималды жұмыс

[ 1,3,2,4,1]
3

Түсіндіру

Не 3 алып тастауға болады, не тең массив жасау үшін 3 қосымша жасауға болады.

[5,3,2,4,1]
4

Түсіндіру

Не 4 алып тастауға болады, не тең массив жасау үшін 4 қосымша жасауға болады.

Барлық элементтерді тең ету үшін минималды амалдарды табу алгоритмі

  1. Декларация а карта.
  2. I <n болған кезде цикл жалғасуда
    1. Массив элементін және әрбір элементтің жиіліктерін картаға сақтаңыз.
  3. жиынтық «MaxCount» 0 үшін.
  4. Егер циклды тексеру арқылы қайталау «MaxCount» картадағы кілт мәнінен аз
    1. Егер шарт қанағаттандырса, онда орнатыңыз «MaxCount» кілт мәніне дейін.
  5. Қайтару (n - “maxCount”).

Түсіндіру

Бізде бар бүтін сан массив кіріс ретінде. Біздің міндетіміз - массивті теңестіру үшін жасалатын минималды амалдарды анықтау. Біз онда картаны қолданамыз. Картаны қолдану арқылы біз элементтерді олардың жиіліктерімен оңай сақтай аламыз, өйткені амалдарды білуде жиіліктер басты рөл атқарады.

Біз максималды жиіліктегі элементті анықтаймыз және жиымның ұзындығы мен жиіліктің максималды саны арасындағы айырмашылықты қайтарамыз, өйткені бізде элемент қайталанатын массивте бар, сондықтан барлық элементтерді бірдей ету үшін аз амалдар қажет өйткені бұл белгілі бір нәрсені өзгерту емес, сондықтан (массивтің ұзындығы - максималды жиілік) осында жұмыс істейді.

Осы жерде бір мысалды қарастырайық:

мысал

arr: {1, 5, 2, 1, 3, 2, 1};

Бірінші элементтен бастап біз бүкіл массивті айналып өтіп, әр элементтің жиілігін санап, оны картаға сақтаймыз.

i = 0,

arr [i] = 1

countFreq = [1: 1]

i = 1

arr [i] = 5

countFreq = [1: 1,5: 1]

i = 2

arr [i] = 2

countFreq = [1: 1,5: 1,2: 1]

i = 3

arr [i] = 1

countFreq = [1: 2,5: 1,2: 1] => Мұнда біз «1» элементін екі рет табамыз, сонда 1 жиілік саны артады.

i = 4

arr [i] = 3

countFreq=[1:2,5:1,2:1,3:1]

i = 5

arr [i] = 2

countFreq = [1: 2,5: 1,2: 2: 3: 1] => Мұнда біз «2» элементін екі рет табамыз, сондықтан жиілік саны 2-ге көбейеді.

i = 6

arr [i] = 1

countFreq = [1: 3,5: 1,2: 2: 3: 1] => Мұнда біз «1» элементін үш рет табамыз, сондықтан жиіліктің саны 1-ге көбейеді.

Енді баптандырыңыз «MaxCount» 0-ге дейін. Әрбір жиілікті тексеріңіз, егер ол үлкен болса «MaxCount», егер үлкенірек деп тапса, онда осы жиіліктің мәнін дейін сақтаңыз «MaxCount»

Ақыр соңында, бізде ең үлкен жиілік болады «MaxCount».

Біз n- ораламыз «MaxCount» => 7-3 = 4, яғни массивті тең ету үшін ең аз дегенде 4 амал жасау керек.

код

Массивтің барлық элементтерін тең ету үшін минималды операцияны табу үшін C ++

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

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

  int maxCount = 0;
  for (auto i : countFreq)
    if (maxCount < i.second)
      maxCount = i.second;

  return (n - maxCount);
}
int main()
{
  int arr[] = {1, 5, 2, 1, 3, 2, 1};
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << getMinimumOperation(arr, n);
  return 0;
}
4

Барлық элементтерді массивке тең ету үшін минималды операцияны табуға арналған Java коды

import java.util.*;
class minimumOperations
{
    public static int getMinimumOperations(int arr[], int n)
    {
        HashMap<Integer, Integer> countFreq = new HashMap<Integer, Integer>();

        for (int i=0; i<n; i++)
        {
            if(countFreq.containsKey(arr[i]))
            {
                countFreq.put(arr[i], countFreq.get(arr[i])+1);
            }
            else
            {
                countFreq.put(arr[i], 1);
            }
        }
        int maxCount = 0;

        Set<Integer> s = countFreq.keySet();

        for (int i : s)
            if (maxCount < countFreq.get(i))
                maxCount = countFreq.get(i);


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

Күрделілікті талдау

Уақыттың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.