Նվազագույն գործողություն `բոլոր տարրերը զանգվածում հավասարեցնելու համար  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Blackrock Միջնաբերդ Դիրեկտի Flipkart Իսկապես Yandex
Դասավորություն Հեշինգ

«Բոլոր տարրերը զանգվածում հավասարեցնելու նվազագույն գործողություն» խնդիրը նշում է, որ ձեզ տրված է դասավորություն ոմանց հետ ամբողջական թվերը դրա մեջ Դուք պետք է պարզեք նվազագույն գործողությունները, որոնք կարելի է անել զանգվածը հավասարեցնելու համար:

Օրինակ  

Նվազագույն գործողություն `բոլոր տարրերը զանգվածում հավասարեցնելու համարPin

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

բացատրություն

Կա՛մ կարող է կատարվել 3 հանում, կա՛մ 3 լրացում ՝ հավասար զանգված կազմելու համար:

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

բացատրություն

Կա՛մ կարող է կատարվել 4 հանում, կա՛մ 4 լրացում ՝ հավասար զանգված կազմելու համար:

Բոլոր տարրերը հավասարեցնելու համար նվազագույն գործողություններ գտնելու ալգորիթմ  

  1. Հայտարարել ա Քարտեզը.
  2. Մինչ ես <n եմ, օղակը շարունակվում է
    1. Քարտեզում պահեք զանգվածի տարրը և յուրաքանչյուր տարրի հաճախականությունները:
  3. հավաքածու «MaxCount» Ինչպես 0:
  4. Կրկնվող օղակի միջոցով ստուգեք, արդյոք «MaxCount» պակաս է, քան քարտեզի բանալին
    1. Եթե ​​պայմանը բավարարում է, ապա դրեք այն «MaxCount» ստեղնի արժեքին:
  5. Վերադարձ (n - «maxCount»):

բացատրություն

Մենք ունենք ամբողջ թիվ դասավորություն որպես մուտքագրում: Մեր խնդիրն է պարզել նվազագույն գործողությունները, որոնք կարելի է անել զանգվածը հավասարեցնելու համար: Մենք պատրաստվում ենք դրա մեջ օգտագործել քարտեզ: Քարտեզի միջոցով մենք կարող ենք հեշտությամբ պահպանել տարրերն իրենց հաճախականություններով, քանի որ հաճախությունները կարևոր դեր են խաղում գործողությունները պարզելու համար:

Տես նաեւ,
Երկուական որոնման ծառի ջնջման գործողություն

Մենք պատրաստվում ենք պարզել առավելագույն հաճախականությամբ տարրը և վերադարձնում ենք զանգվածի երկարության և առավելագույն հաճախականության հաշվարկի տարբերությունը, որովհետև մենք արդեն ունենք զանգվածի այն տարրը, որը կրկնվում է, ուստի բոլոր տարրերը նույնը դարձնելու համար ավելի քիչ գործողություններ են պետք: քանի որ դա ավելի շուտ փոխում է, քան որոշակի առանձնահատկություն փոխելը, և այդ պատճառով (զանգվածի երկարությունը - առավելագույն հաճախականությունը) այն աշխատում է այստեղ:

Եկեք այստեղ քննարկենք մի օրինակ.

Օրինակ

arr ՝ {1, 5, 2, 1, 3, 2, 1};

Սկսած ամենաառաջին տարրից `մենք անցնում ենք ամբողջ զանգվածը և հաշվում յուրաքանչյուր տարրի հաճախականությունը և պահում այն ​​քարտեզի վրա:

ես = 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

Բարդության վերլուծություն  

Timeամանակի բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Տես նաեւ,
Գտեք տրված գումարով զույգեր այնպես, որ զույգի տարրերը լինեն տարբեր շարքերում

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: