Рубрики

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

Дан массив из n элементов, так что элементы могут повторяться. Мы можем удалить любое количество элементов из массива. Задача состоит в том, чтобы найти минимальное количество элементов, которые будут удалены из массива, чтобы сделать его равным.

Примеры:

Input  : arr[] = {4, 3, 4, 4, 2, 4}
Output : 2
After deleting 2 and 3 from array, array becomes 
arr[] = {4, 4, 4, 4} 

Input : arr[] = {1, 2, 3, 4, 5}
Output: 4
We can delete any four elements from array.

В этой проблеме нам нужно минимизировать операции удаления. Подход прост: мы подсчитываем частоту каждого элемента в массиве, а затем находим частоту наиболее частого элемента в массиве отсчетов . Пусть эта частота будет max_freq. Чтобы получить минимальное количество элементов, которые будут удалены из массива, вычислите n — max_freq, где n — количество элементов в данном массиве.

// 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[] = {4, 3, 4, 4, 2, 4};

    int n = sizeof(arr)/sizeof(arr[0]);

    cout << minDelete(arr, n);

    return 0;

}

Выход:

2

Временная сложность: O (n)

Примечание: здесь мы можем оптимизировать дополнительное пространство для подсчета частоты каждого элемента до O (1), но для этого мы должны изменить наш исходный массив. Смотрите эту статью.

Эта статья предоставлена Шашанком Мишрой (Гуллу) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

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

0.00 (0%) 0 votes