Мінімальна операція для зрівняння всіх елементів у масиві  


Рівень складності Легко
Часто запитують у Амазонка BlackRock Цитадель Directi Flipkart Дійсно Яндекс
масив Хешування

Проблема "Мінімальна операція з метою зрівняння всіх елементів у масиві" стверджує, що вам дано масив з деякими цілих чисел у цьому. Ви повинні з’ясувати мінімальні операції, які можна зробити, щоб зробити масив рівним.

Приклад PinPinPinPin PinPinPinPin

Мінімальна операція для зрівняння всіх елементів у масивіPin

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

Пояснення

Можна зробити 3 віднімання або 3 складання, щоб отримати рівний масив.

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

Пояснення

Можна зробити 4 віднімання або 4 складання, щоб отримати рівний масив.

Алгоритм пошуку мінімальних операцій для зрівняння всіх елементів PinPinPinPin PinPinPinPin

  1. Заявіть a карта.
  2. Поки i <n, цикл продовжується
    1. Збережіть елемент масиву та частоти кожного елемента на карті.
  3. Установка “MaxCount” в 0.
  4. Переглядаючи цикл, перевірте, якщо “MaxCount” менше значення ключа на карті
    1. Якщо умова задовольняє, встановіть “MaxCount” до значення ключа.
  5. Повернення (n - “maxCount”).

Пояснення

У нас є ціле масив як вхід. Наше завдання - з’ясувати мінімальні операції, які можна зробити, щоб зробити масив рівним. Ми збираємось використовувати в ньому карту. Використовуючи карту, ми можемо легко зберігати елементи з їх частотами, оскільки частоти відіграють ключову роль для з’ясування операцій.

Ми збираємось виявити елемент з максимальною частотою, і ми повертаємо різницю між довжиною масиву та максимальним підрахунком частоти, оскільки ми вже маємо елемент у масиві, який повторюється, тому потрібно менше операцій, щоб зробити всі елементи однаковими як це, а не змінюючи конкретний, і тому (довжина масиву - максимальна частота) він працює тут.

Дивись також
Операція видалення бінарного дерева пошуку

Розглянемо тут приклад:

Приклад

обр .: {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 операції, щоб масив став рівним.

код PinPinPinPin PinPinPinPin

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

Аналіз складності PinPinPinPin PinPinPinPin

Складність часу

О (п) де "N" - кількість елементів у масиві.

Дивись також
Знайдіть пари з заданою сумою, щоб елементи пари знаходились у різних рядках

Складність простору

О (п) де "N" - кількість елементів у масиві.