سڀني عنصرن کي صف ۾ برابر بڻائڻ لاءِ گهٽ ۾ گهٽ آپريشن


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Amazon ڪاروڪ قلعي سڌو فلپٽٽ يقينا ياندڪس
ڪيريو هاشمي

مسئلو ”گهٽ ۾ گهٽ آپريشن سڀني عنصرن کي برابر ۾ رکڻ“ جو بيان آهي ته توهان کي هڪ ڏنو ويو آهي صف ڪجهه سان جيتريون ان ۾. توهان کي گهٽ ۾ گهٽ آپريشنون ڳولهڻيون پونديون جيڪي هڪ صف برابر ڪرڻ لاءِ ڪري سگهجن ٿيون.

مثال

سڀني عنصرن کي صف ۾ برابر بڻائڻ لاءِ گهٽ ۾ گهٽ آپريشن

[ 1,3,2,4,1]
3

وضاحت

يا 3 سرشار ڪم ڪري سگھجن ٿا يا برابر اضافو ڪرڻ لاءِ 3 واڌارا ڪري سگھجن ٿيون.

[5,3,2,4,1]
4

وضاحت

يا 4 سرشار ڪم ڪري سگھجن ٿا يا برابر اضافو ڪرڻ لاءِ 4 واڌارا ڪري سگھجن ٿيون.

الگورٿم سڀني عنصرن کي برابر بڻائڻ لاءِ آپريشن کي ڳولڻ

  1. اعلان ڪيو اي نقشي.
  2. جڏهن مان i <، لوپ جاري رهي ٿو
    1. نقشي ۾ ھر عنصر جي ترتيب وارو عنصر ۽ تعدد محفوظ ڪريو.
  3. مقرر وڌ کان وڌ 0 تائين
  4. جيڪڏهن چڪاس ٿئي ته لوپ جي چڪاس مٿان وڌ کان وڌ ھڪڙي نقشي ۾ چاٻي جي قيمت کان گھٽ آھي
    1. جيڪڏهن شرط مطمئن هجي ، ته پوءِ سيٽ ڪريو وڌ کان وڌ ڪيچ جي قيمت
  5. واپسي (ن - “وڌ کان وڌ”).

وضاحت

اسان وٽ هڪ آهي انٽرويو صف انپٽ جي طور تي. اسان جو ڪم اهو آهي ته گهٽ ۾ گهٽ آپريشن کي ڳوليون وڃي جيڪو هڪ برابر بڻائڻ جي لاءِ ٿي سگهي ٿو. اسان انهي ۾ هڪ نقشو استعمال ڪرڻ وارا آهيون. هڪ نقشو استعمال ڪندي ، اسان آساني سان عناصر پنهنجي تعدد سان محفوظ ڪري سگهندا آهيون ، ڇاڪاڻ ته تعدد آپريشن کي معلوم ڪرڻ ۾ اهم ڪردار ادا ڪندا آهن.

اسان عنصر کي وڌ کان وڌ فریکوئنسي سان معلوم ڪرڻ وارا آهيون ۽ اسان صف جي ڊيگهه ۽ وڌ کان وڌ فریکوئنسي ڳڻپ جي وچ ۾ فرق واپس آڻيندا آهيون ڇاڪاڻ ته اسان جو عنصر پهرين ئي صف ۾ آهي جيڪو بار بار ڪيو ويندو آهي تنهن ڪري هن سڀني عنصرن کي هڪجهڙو بڻائڻ لاءِ گهٽ آپريشن ڪيا ويندا آهن. جيئن ته اهو هڪ خاص بدلائڻ جي بدران آهي ۽ اهو ئي سبب آهي (صف جي ڊيگهه- وڌ کان وڌ فریکوئنسي) اهو هتي ڪم ڪري ٿو.

اچو ته هتي هڪ مثال تي غور ڪريون.

مثال

arr: {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 جي فريڪوئنسي ڳڻپ ۾ اضافو ٿيندو

ھاڻي شروعاتي ڪر وڌ کان وڌ 0. ۽ هر فریکوئنسي کي پڙتال ڪريو ته اها وڌيڪ آهي وڌيڪ وڌ کان وڌجيڪڏهن گهڻي کان وڏي هجڻ جي ڳولا ڪن ، ته کان انهي تعدد جي قيمت کي محفوظ ڪريو وڌ کان وڌ

آخر ۾ ، اسان جي سڀ کان وڏي تعدد هوندي وڌ کان وڌ.

اسين موٽون ٿا n- وڌ کان وڌ => 7-3 = 4 ، اهو آهي ته اسان صف کي برابر بڻائڻ لاءِ 4 آپريشن ڪرڻ گهرجن.

ڪوڊ

سي ++ سڀني عنصرن کي صف ۾ برابر بڻائڻ لاءِ گهٽ ۾ گهٽ آپريشن ڳولڻ لاءِ

#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

جاوا ڪوڊ گهٽ ۾ گهٽ آپريشن ڳولڻ لاءِ سمورن عنصرن کي برابر بڻائڻ لاءِ

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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.

خلائي پيچيدگي

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.