لږترلږه عملیات حذف کړئ ترڅو د صفر ورته عناصرو ټول توکي رامینځته کړئ  


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ایڈوب حقیقت
پیشه هاش

فرض کړئ چې موږ د دې وسیله لرو سور سره "ایکس" د عناصرو شمیر. موږ یوه ستونزه راکړې چې موږ باید د حذف عملیات ومومو ، کوم چې باید لږترلږه وي چې د مساوي سرلیک جوړولو لپاره اړین دی ، لکه سرنی به مساوي عناصر ولري.

بېلګه  

تفتیش:

[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" ته INT_MIN.
  3. په نقشه کې تفتیش وکړئ او وګورئ چې کوم عنصر اعظمي فریکونسۍ لري.
    • ټاکل شوی "max_freq" ته اعظمي (اعظمي_ فريق ، ارزښت) ترڅو د ټولو فریکونسیو تر مینځ اعظمي ارزښت ومومئ.
  4. د صف د اندازې تر مینځ توپیر راوباسي "n" او max_freq (n - max_freq).

تشریح  

موږ یوه ستونزه درکړه چې په هغه کې موږ باید معلومه کړو چې لږترلږه څو ړنګول عملیات اړین دی د یو برابر مساوي کولو لپاره (ورته عناصرو). د دې لپاره ، موږ د ذخیره کولو لپاره نقشه وکاروو تعددونه د هرې شمیرې چې په صف کې شتون لري.

هم وګوره
د هر کرکټر ځای په ځای کولو پوښتنې وروسته د پالینډروم لپاره چیک کړئ

د دې کولو سره ، موږ به دا فریکونسۍ ولرو چې د ټولو فریکونسیونو ترټولو لوی دی. د نقشه په تکرار سره ، موږ د اعظمي میتود په کارولو سره دا اعظمي تعدد ترلاسه کولی شو. د تکرار وروسته نقشه موږ به اعظمي فریکونسۍ ولرو او موږ اړتیا لرو د سرې_ اندازې - اعظمي فریکوینسي بیرته راولو ، دا پدې مانا ده چې موږ د لږ شمیر فریکونسیو ټولټال بیرته راستنیدو سره چې لرې کیدی شي د صف برابر کولو لپاره.

راځئ چې یوه بېلګه په نظر کې ونیسو:

تیر: {10 ، 3 ، 4 ، 4 ، 2 ، 4}؛

  • i = 0 ، دا د آر په توګه اخلي [i] د 10 په څیر او پلورنځی (10 ، 1).
  • i = 1 ، دا د آر په توګه اخلي [i] د 3 په څیر او پلورنځی (3 ، 1).
  • د i = 2 لپاره ، دا آرر [i] د 4 په څیر اخلي او فریک (سټور 4 ، 1) اخلي.
  • i = 3 ، دا آرور نیسي [i] د 4 په څیر ، ځکه چې 4 لا دمخه په نقشه کې ځای لري دا یوازې د 4 کلیدي ځای کې یو بل شمیره اضافه کوي او د ذخیره freq (4 ، 2).
  • i = 4 ، دا آرر اخلي [i] د 2 په څیر او د فریکو ذخیره (2 ، 1).
  • د i = 5 لپاره ، دا آرور اخلي [i] د 4 په څیر ، ځکه چې 4 لا دمخه په نقشه کې ځای لري دا یوازې د 4 کلیدي ځای کې یو بل شمیره اضافه کوي او د ذخیره فریق (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

د لږترلږه حذف عملیاتو لپاره جاوا برنامې ترڅو د صفر ورته عناصرو ټول عناصر رامینځته کړي

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

د لږترلږه حذف عملیاتو لپاره د پیچلتیا تحلیل ترڅو د صفې ورته عناصرو ټول عناصر رامینځته کړي  

د وخت پیچلتیا

O (n) چیرې "n" په صف کې د عناصرو شمیر دی

هم وګوره
وګورۍ چې سرلیکونه د اجازه ورکړل شوي نقلونو سره متقابل تعدد لري

د ځای پیچلتیا

O (n) چیرې "n" په صف کې د عناصرو شمیر دی