მინიმალური წაშალეთ ოპერაციები, რათა მასივის ყველა ელემენტი ერთნაირი იყოს  


Რთული ტური Easy
ხშირად ეკითხებიან Adobe ფაქტები
Array Hash

დავუშვათ, რომ ჩვენ გვაქვს შეყვანა მასივი ერთად "X" ელემენტების რაოდენობა. ჩვენ დავაყენეთ პრობლემა, რომ უნდა ვიპოვოთ წაშლის ოპერაციები, რაც უნდა იყოს მინიმალური, რაც საჭიროა ტოლი მასივის შესაქმნელად, ანუ, მასივი შედგება თანაბარი ელემენტებისგან.

მაგალითი  

შეყვანის:

[1, 1, 4, 6, 2, 1]

გამოყვანის:

3

განმარტება:

(4, 6, 2) 3 ელემენტის ამოღების შემდეგ მასივი ხდება ტოლი, ანუ, [1, 1, 1]

შეყვანის:

[1, 5, 4, 16, 32, 9]

გამოყვანის:

5

განმარტება:

ჩვენ შეგვიძლია ამოვიღოთ 5 ელემენტიდან რომელიმე, რომ გახდეს თანაბარი მასივი.

ალგორითმი  

  1. შეინახეთ მასივის ყველა ელემენტის სიხშირე რუკაზე.
  2. უცნობია "Max_freq" to INT_MIN.
  3. გაიმეორეთ რუქა და შეამოწმეთ რომელ ელემენტს აქვს მაქსიმალური სიხშირე.
    • უცნობია "Max_freq" to მაქს (max_freq, მნიშვნელობა) ყველა სიხშირეს შორის მაქსიმალური მნიშვნელობის პოვნა.
  4. დააბრუნე განსხვავება მასივის ზომას შორის "ნ" და max_freq (n - max_freq).

განმარტება  

ჩვენ მივეცით პრობლემა, რომელშიც უნდა გავერკვეთ რამდენი მინიმუმი წაშლა საჭიროა ოპერაციები, რათა მასივი იყოს ტოლი (მსგავსი ელემენტების). ამისათვის ჩვენ ვიყენებთ რუკის შესანახად სიხშირეზე თითოეული რიცხვი, რომელიც მასივშია.

იხილეთ ასევე
შეამოწმეთ Palindrome სიმბოლოების ყოველი ჩანაცვლების შემდეგ

ამით ჩვენ გვექნება ის სიხშირე, რომელიც ყველაზე დიდია ყველა სიხშირეს შორის. რუკის განმეორებით, მაქსიმალური სიხშირის მიღება მაქსიმალური მეთოდის გამოყენებით შეგვიძლია. განმეორების შემდეგ რუკა ჩვენ გვექნება მაქსიმალური სიხშირე და უნდა დავაბრუნოთ array_size - მაქსიმალური სიხშირე, ეს ნიშნავს, რომ ვიბრუნებთ ნაკლები სიხშირეების საერთო რაოდენობას, რომელთა ამოღება შესაძლებელია, რათა მასივი გახდეს თანაბარი.

განვიხილოთ მაგალითი:

arr: {10, 3, 4, 4, 2, 4};

  • i = 0, მას სჭირდება arr [i] 10 და ინახავს freq (10, 1).
  • i = 1, მას სჭირდება arr [i] 3 და ინახავს freq (3, 1).
  • i = 2-ისთვის, arr [i] - ს 4 სჭირდება და freq (4, 1) ინახავს.
  • i = 3, ეს arr [i] 4-ს იღებს, რადგან 4-ს უკვე აქვს ადგილი რუქაზე, ის უბრალოდ მატებს კიდევ ერთ რიცხვს 4-ის საკვანძო ადგილას და ინახავს freq- ს (4, 2).
  • i = 4, მიიღებს arr [i] როგორც 2 და შეინახავს freq (2, 1).
  • i = 5-ისთვის, arr [i] - ს 4-ს სჭირდება, რადგან 4-ს უკვე აქვს ადგილი რუქაზე, ის უბრალოდ მატებს კიდევ ერთ რიცხვს 4-ის საკვანძო ადგილას და ინახავს freq- ს (4, 3).

ამ ყველაფერში მხოლოდ '4' -ს აქვს მაქსიმალური სიხშირე, რომელიც არის 3 და რუქიდან და მაქსიმალური სიხშირის 3-ის პოვნადან, ჩვენ ვაპირებთ მნიშვნელობის დაბრუნებას (n - max_freq) 3. ეს არის ჩვენი შედეგი.

განხორციელება  

C ++ პროგრამა მინიმალური წაშლის ოპერაციებისათვის, რათა მასივის ყველა ელემენტი ერთნაირი იყოს

#include <bits/stdc++.h>
using namespace std;

int minDelete(int arr[], int n)
{
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;

    int max_freq = INT_MIN;

    for (auto itr = freq.begin(); itr != freq.end(); itr++)
        max_freq = max(max_freq, itr->second);

    return n - max_freq;
}
int main()
{
    int arr[] = { 10, 3, 4, 4, 2, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minDelete(arr, n);
    return 0;
}
3

Java პროგრამა მინიმალური წაშლის ოპერაციებისათვის, რათა მასივის ყველა ელემენტი ერთნაირი იყოს

import java.util.HashMap;
class minimumDeletionOperation
{
    public static int noOfMinimumDeletions(int arr[], int n)
    {
        HashMap<Integer,Integer> freq=new HashMap<Integer,Integer>();
        for(int i=0; i<arr.length; i++)
        {
            if(freq.containsKey(arr[i]))
                freq.put(arr[i], freq.get(arr[i]) + 1);
            else
                freq.put(arr[i], 1);
        }

        int max_freq=Integer.MIN_VALUE;

        for (int i:freq.keySet())
            max_freq = Math.max(max_freq, freq.get(i));

        return n - max_freq;
    }
    public static void main(String args[])
    {
        int arr[] = { 10, 3, 4, 4, 2, 4 };
        int n = arr.length;
        System.out.println(noOfMinimumDeletions(arr, n));
    }
}
3

სირთულის ანალიზი მინიმალური წაშლის ოპერაციებისათვის, რათა მასივის ყველა ელემენტი ერთნაირი იყოს  

დროის სირთულე

ო (ნ) სად "ნ" არის მასივის ელემენტების რაოდენობა

იხილეთ ასევე
შეამოწმეთ, შეიცავს თუ არა მასივი ნებადართულ დუბლიკატებთან მომიჯნავე მთელი რიცხვები

სივრცის სირთულე

ო (ნ) სად "ნ" არის მასივის ელემენტების რაოდენობა