الحد الأدنى من العملية لجعل جميع العناصر متساوية في المصفوفة  


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون بلاك روك قلعة Directi Flipkart في الواقع ياندكس
مجموعة تجزئة

توضح مشكلة "الحد الأدنى للعملية لجعل جميع العناصر متساوية في المصفوفة" أنك تحصل على الامتداد مجموعة مع بعض الأعداد الصحيحة فيه. عليك معرفة الحد الأدنى من العمليات التي يمكن إجراؤها لجعل المصفوفة متساوية.

مثال  

الحد الأدنى من العملية لجعل جميع العناصر متساوية في المصفوفةدبوس

[ 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”).

تفسير

لدينا عدد صحيح مجموعة كمدخل. مهمتنا هي معرفة الحد الأدنى من العمليات التي يمكن إجراؤها لجعل المصفوفة متساوية. سنستخدم خريطة فيه. باستخدام الخريطة ، يمكننا بسهولة تخزين العناصر بتردداتها ، لأن الترددات تلعب دورًا رئيسيًا في اكتشاف العمليات.

انظر أيضا
عملية حذف شجرة البحث الثنائية

سنكتشف العنصر ذي التردد الأقصى ونعيد الفرق بين طول المصفوفة والحد الأقصى لعدد الترددات لأن لدينا العنصر بالفعل في مصفوفة يتم تكراره لذا يتطلب الأمر عمليات أقل لجعل جميع العناصر كما هي لأنه بدلاً من تغيير معين ولهذا (طول المصفوفة - الحد الأقصى للتردد) يعمل هنا.

دعونا نفكر في مثال هنا:

مثال

وصول: {1، 5، 2، 1، 3، 2، 1} ؛

بدءًا من أول عنصر ، نجتاز المصفوفة بأكملها ونحسب تكرار كل عنصر ونخزنه على الخريطة.

أنا = 0 ،

arr [i] = 1

countFreq = [1: 1]

ط = 1

arr [i] = 5

countFreq = [1: 1,5،1: XNUMX]

ط = 2

arr [i] = 2

countFreq = [1: 1,5،1,2: 1،XNUMX: XNUMX]

ط = 3

arr [i] = 1

countFreq = [1: 2,5،1,2: 1،1: 1] => هنا سنجد العنصر "XNUMX" مرتين ، لذا سنزيد عدد التكرار XNUMX.

ط = 4

arr [i] = 3

countFreq=[1:2,5:1,2:1,3:1]

ط = 5

arr [i] = 2

countFreq = [1: 2,5،1,2: 2،3: 1: 2: 2] => هنا سنجد العنصر "XNUMX" مرتين ، لذا سنزيد عدد الترددات بمقدار XNUMX.

ط = 6

arr [i] = 1

countFreq = [1: 3,5،1,2: 2،3: 1: 1: 1] => هنا سنجد العنصر "XNUMX" ثلاث مرات ، لذلك سيزيد عدد الترددات بمقدار XNUMX.

الآن التهيئة "maxCount" إلى 0. وتحقق من كل تردد إذا كان أكبر من "maxCount"، إذا كانت النتائج أكبر ، فقم بتخزين قيمة هذا التردد في "maxCount"

أخيرًا ، سيكون لدينا أكبر تردد في "maxCount".

نعود ن- "maxCount" => 7-3 = 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 (ن) أين "ن" هو عدد العناصر في الصفيف.

انظر أيضا
ابحث عن أزواج بمجموع معين بحيث تكون عناصر الزوج في صفوف مختلفة

تعقيد الفضاء

O (ن) أين "ن" هو عدد العناصر في الصفيف.