Минимум операций удаления, чтобы сделать все элементы массива одинаковыми


Сложный уровень Легко
Часто спрашивают в саман Набор фактов
массив Hash

Предположим, у нас есть вход массив с "Х" количество элементов. Мы поставили задачу найти операции удаления, которые должны быть минимумом, необходимым для создания равного массива, т.е. массив будет состоять из равных элементов.

Пример

Входной сигнал:

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

Вывод:

3

Объяснение:

После удаления (4, 6, 2) 3 элементов массив становится равным, то есть [1, 1, 1]

Входной сигнал:

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

Вывод:

5

Объяснение:

Мы можем удалить любой из 5 элементов, чтобы сделать его равным массивом.

Алгоритм

  1. Сохраните частоты всех элементов массива на карте.
  2. Набор «Max_freq» в INT_MIN.
  3. Просмотрите карту и проверьте, какой элемент имеет максимальную частоту.
    • Набор «Max_freq» в max (max_freq, значение) найти максимальное значение среди всех частот.
  4. Вернуть разницу между размером массива «Н» и max_freq (n - max_freq).

объяснение

Мы поставили задачу, в которой мы должны выяснить, сколько минимальных удаление операции необходимы, чтобы сделать массив равным (из похожих элементов). Для этого мы будем использовать карту для хранения Частоты каждого числа, присутствующего в массиве.

Таким образом мы получим самую большую частоту среди всех частот. Путем итерации по карте мы можем получить эту максимальную частоту с помощью метода max. После итерации карта у нас будет максимальная частота, и нам нужно вернуть array_size - максимальную частоту, это означает, что мы возвращаем общее количество меньших частот, которые можно удалить, чтобы сделать массив равным.

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

обр .: {10, 3, 4, 4, 2, 4};

  • i = 0, arr [i] принимает значение 10 и сохраняет частоту (10, 1).
  • i = 1, arr [i] принимает значение 3 и сохраняет частоту (3, 1).
  • для i = 2 он принимает arr [i] как 4 и сохраняет freq (4, 1).
  • i = 3, он принимает arr [i] как 4, поскольку 4 уже имеет место на карте, он просто добавляет еще один счетчик в ключевом месте 4 и сохраняет freq (4, 2).
  • i = 4, он принимает arr [i] как 2 и сохраняет freq (2, 1).
  • для i = 5 он принимает arr [i] как 4, поскольку 4 уже имеет место на карте, он просто добавляет еще один счетчик в ключевом месте 4 и сохраняет freq (4, 3).

Среди всего этого только число '4' имеет максимальную частоту, равную 3, и после прохождения и нахождения максимальной частоты как 3 на карте мы собираемся вернуть значение (n - max_freq) 3. Это наш результат.

Реализация

Программа на C ++ для минимальных операций удаления, чтобы все элементы массива были одинаковыми

#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

Программа на Java для минимальных операций удаления, чтобы все элементы массива были одинаковыми

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

Анализ сложности для минимума операций удаления, чтобы все элементы массива были одинаковыми

Сложность времени

O (n) где «Н» это количество элементов в массиве

Космическая сложность

O (n) где «Н» это количество элементов в массиве