最少的删除操作,以使数组的所有元素相同


难度级别 易得奖学金
经常问 土砖 事实集
排列 哈希

假设我们有一个输入 排列“x”的 元素数量。 我们已经提出了一个问题,我们必须找到删除操作,该操作应该是制作相等数组所需的最小值,即该数组将由相等的元素组成。

使用案列

输入:

[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. 返回数组大小之间的差 “ n”max_freq(n – max_freq).

说明

我们提出了一个问题,我们必须找出最小数量 缺失 需要进行运算以使数组相等(由相似元素组成)。 为此,我们将使用地图来存储 频率 数组中存在的每个数字中的一个。

这样,我们将获得在所有频率中最大的频率。 通过遍历地图,我们可以使用max方法获得最大频率。 迭代后 地图 我们将拥有最大频率,我们需要返回array_size –最大频率,这意味着我们将返回可以删除以使数组相等的较小频率的总数。

让我们考虑一个例子:

arr:{10、3、4、4、2、4};

  • i = 0,它将arr [i]设为10并存储freq(10,1)。
  • i = 1,它将arr [i]设为3并存储freq(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)其中 “ n” 是数组中元素的数量

空间复杂度

O(n)其中 “ n” 是数组中元素的数量