Bütün elementləri massivdə bərabərləşdirmək üçün minimum əməliyyat

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon BlackRock Citadel Directi Flipkart Həqiqətən Yandex
Geyim HashingBaxılıb 115

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

“Bütün elementləri massivdə bərabərləşdirmək üçün minimum əməliyyat” problemi sizə bir verildiyini bildirir array bəziləri ilə tamsayılar içində. Bir sıra bərabərləşdirmək üçün edilə biləcək minimum əməliyyatları tapmalısınız.

misal

Bütün elementləri massivdə bərabərləşdirmək üçün minimum əməliyyatPin

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

Izahat

Ya 3 toplama əməliyyatı edilə bilər, ya da bərabər bir sıra etmək üçün 3 əlavə edilə bilər.

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

Izahat

Ya 4 toplama əməliyyatı edilə bilər, ya da bərabər bir sıra etmək üçün 4 əlavə edilə bilər.

Bütün elementləri bərabərləşdirmək üçün minimum əməliyyatları tapmaq üçün alqoritm

  1. Bəyan edin a xəritə.
  2. İ <n ikən, döngə davam edir
    1. Massiv elementini və hər elementin tezliklərini xəritədə saxlayın.
  3. Set “MaxCount” 0 üçün.
  4. Döngü yoxlayın “MaxCount” xəritədəki düymənin dəyərindən azdır
    1. Şərt təmin edərsə, qoyun “MaxCount” açarın dəyərinə.
  5. Geri qayıt (n - “maxCount”).

Izahat

Bir var tam array giriş olaraq. Bizim vəzifəmiz bir sıra bərabərləşdirmək üçün ediləcək minimum əməliyyatları tapmaqdır. İçində bir xəritədən istifadə edəcəyik. Bir xəritə istifadə edərək elementləri tezlikləri ilə asanlıqla saxlaya bilərik, çünki əməliyyatları tapmaq üçün tezliklər əsas rol oynayır.

Maksimum tezlikli elementi tapacağıq və massivin uzunluğu ilə maksimum tezlik sayımı arasındakı fərqi qaytarırıq, çünki element artıq bir sıra içindədir, buna görə bütün elementləri eyni etmək üçün daha az əməliyyat lazımdır bir konkreti dəyişdirmək əvəzinə və burada işləməsinin səbəbi (massivin uzunluğu - maksimum tezlik).

Burada bir nümunəni nəzərdən keçirək:

misal

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

İlk ən çox elementdən başlayaraq bütün massivi dolaşırıq və hər elementin tezliyini sayırıq və xəritədə saxlayırıq.

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] => Burada “1” elementini iki dəfə tapacağıq, beləliklə 1-in sayını artıracağıq.

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] => Burada “2” elementini iki dəfə tapacağıq, beləliklə 2-nin sayını artıracağıq.

i = 6

arr [i] = 1

countFreq = [1: 3,5: 1,2: 2: 3: 1] => Burada üç dəfə “1” elementini tapacağıq, beləliklə 1-in sayını artıracağıq.

İndi başlayın “MaxCount” -dən 0.-a qədər və hər bir tezliyi yoxlayın “MaxCount”, daha böyük olduğunu taparsa, o tezliyin dəyərini “MaxCount”

Nəhayət, ən böyük tezliyə sahib olacağıq “MaxCount”.

N- qayıdırıq “MaxCount” => 7-3 = 4, yəni massivi bərabərləşdirmək üçün minimum 4 əməliyyat etməliyik.

Kodu

Bütün elementləri massivdə bərabərləşdirmək üçün minimum əməliyyatı tapmaq üçün 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

Bütün elementləri massivdə bərabərləşdirmək üçün minimum əməliyyatı tapmaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara "N" massivdəki elementlərin sayıdır.

Kosmik Mürəkkəblik

O (n) hara "N" massivdəki elementlərin sayıdır.

Crack Sistemi Dizayn Müsahibələri
Translate »