Минимална операция, за да се направят всички елементи равни в масива  


Ниво на трудност Лесно
Често задавани в Амазонка BlackRock Цитадела Директи Flipkart Наистина Yandex
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

Анализ на сложността щифтщифтщифтщифт щифтщифтщифтщифт

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

О (п) където "н" е броят на елементите в масива.

Вижте също
Намерете двойки с дадена сума, така че елементите на двойка да са в различни редове

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

О (п) където "н" е броят на елементите в масива.