使数组中的所有元素相等的最小操作  


难度级别 易得奖学金
经常问 亚马逊 贝莱德 堡垒 指令 Flipkart 的确 Yandex的
排列 哈希

问题“使数组中的所有元素相等的最小操作”指出给您一个 排列 和一些 整数 在里面。 您必须找出可以使数组相等的最小操作。

使用案列  

使数组中的所有元素相等的最小操作

[ 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

复杂度分析  

时间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。

参见
查找具有给定总和的对,从而使对中的元素位于不同的行中

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。