Массивде бардык элементтерди бирдей кылуу үчүн минималдуу иш


Кыйынчылык деңгээли жеңил
Көп суралган Amazon Кара таш Citadel Directi Flipkart Чындыгында Яндекс
согуштук тизме Hashing

Массивде "бардык элементтерди бирдей кылуу үчүн минималдуу иш" көйгөйү сизге берилет согуштук тизме кээ бирлери менен бүтүн ичинде. Массивди барабар кылуу үчүн жасала турган минималдуу амалдарды табышыңыз керек.

мисал

Массивде бардык элементтерди бирдей кылуу үчүн минималдуу иш

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

түшүндүрүү

Же 3 кемитүүнү жасоого болот же бирдей массивди түзүү үчүн 3 толуктоону жасоого болот.

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

түшүндүрүү

Же 4 кемитүүнү жасоого болот же бирдей массивди түзүү үчүн 4 толуктоону жасоого болот.

Бардык элементтерди бирдей кылуу үчүн минималдуу амалдарды табуу алгоритми

  1. Декларация a карта.
  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" массивдеги элементтердин саны.