使數組中的所有元素相等的最小操作  


難度級別 容易獎學金
經常問 亞馬遜 貝萊德 堡壘 指令 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” 是數組中元素的數量。