دو عناصر کی تعدد کے مابین زیادہ سے زیادہ فرق جیسے عنصر کی کثرت تعدد بھی زیادہ ہے  


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایکسینچر اکٹھا کرنا ایمیزون VMware
لڑی ہیش چھانٹ

فرض کیج. ، آپ کا ایک عدد صحیح ہے صف. مسئلہ بیان کسی دیئے گئے صف کے کسی بھی دو الگ عناصر کی تعدد کے مابین زیادہ سے زیادہ فرق معلوم کرنے کے لئے کہتا ہے ، لیکن زیادہ تعدد والا عنصر بھی دوسرے عدد کے مقابلے میں قدر میں زیادہ ہونا چاہئے۔

مثال کے طور پر  

ان پٹ:

ارر [] = {2,4,4,4,3,2،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

: پیداوار

2

وضاحت:

4 → 3 کی تعدد

2 → 2 کی تعدد

اور 3 → 1 کی تعدد

4 (3) - 3 (1) = 2 (عدد بھی زیادہ سے زیادہ اور زیادہ سے زیادہ تعدد ہیں)۔

الگورتھم  

  1. اعلان a نقشہ اور ایک صف کی لمبائی کا 'فاصلہ' کہتے ہیں۔
  2. گنیں اور اسٹور کریں عناصر کی تعدد نقشہ میں اور ایک ساتھ سرنی کی اقدار کو فاصلہ صف میں محفوظ کریں۔
  3. فاصلہ صف کو ترتیب دیں۔
  4. کم سے کم n + 1 اور آؤٹ پٹ 0 پر سیٹ کریں۔
  5. صف کو عبور کریں ، جبکہ میں
    1. آؤٹ پٹ اور فاصلے کی قدر کے درمیان زیادہ سے زیادہ فرق [i] اور کم سے کم تلاش کریں اور اسے آؤٹ پٹ میں اسٹور کریں۔
    2. کم سے کم اور فاصلے کی قدر کے درمیان کم سے کم تلاش کریں [i] اور اسے کم سے کم اسٹور کریں۔
  6. واپسی کی واپسی

وضاحت  

ہمیں ایک عدد اعداد دی جاتی ہے اور ہمیں دو عناصر کی فریکوئنسی کے درمیان زیادہ سے زیادہ فرق معلوم کرنے کی ضرورت ہوتی ہے تاکہ عنصر زیادہ فریکوئنسی والے کسی دوسرے عدد سے بھی کم اور کم تعدد والے عدد سے بھی زیادہ ہونا چاہئے۔ ہم استعمال کرنے جا رہے ہیں ہیکنگ اور چھانٹ جو موثر کوڈ بنانے میں ہماری مدد کرے گا۔ سب سے پہلے ، ہم ایک نقشہ اور ایک انٹیجر ارے کا اعلان کریں گے جس کو فاصلہ کہا جاتا ہے جس طرح دیئے گئے صفوں کے ساتھ اسی سائز کے ساتھ فاصلہ کہا جاتا ہے۔

یہ بھی دیکھتے ہیں
گراف کے لئے بریڈتھ فرسٹ سرچ (بی ایف ایس)

سرنی عناصر کی فریکوئینسی کو اسٹور کرنے اور گننے کے ل the سرے کی سیر کرتے ہوئے ہمیں اپنے الگورتھم کے مطابق صف کی قیمت [i] بھی ذخیرہ کرنے کی ضرورت ہے۔ ہم آؤٹ پٹ کی قدر 0 اور کم سے کم n + 1 پر رکھیں گے۔ یہ کم سے کم قیمت ہمیں تمام تعدد کے درمیان کم سے کم معلوم کرنے میں مدد کرتی ہے ، اور آؤٹ پٹ متغیر میں ، ہم اپنا زیادہ سے زیادہ فرق ذخیرہ کرنے جارہے ہیں۔ اب ، ہمیں سرنی کو ترتیب دینے کی ضرورت ہے جس میں ہم اقدار (فاصلہ صف) محفوظ کرتے ہیں۔

ہم اب فاصلہ صف کو عبور کریں گے اور ہمیں ویلیو j تک کو عبور کرنے کی ضرورت ہے کیونکہ پچھلے ٹروراسال میں جب ہم فاصلے میں ویلیوز کو اسٹور کرتے ہیں تو ہم j کی ویلیو بڑھا رہے تھے ، لہذا j کی قدر فاصلے کے لئے زیادہ سے زیادہ ویلیو ہے صف عبور کرنے کے لئے. ہمیں پیداوار اور تعدد اور کم سے کم قیمت کے درمیان فرق کے درمیان زیادہ سے زیادہ فاصلہ تلاش کرنے کی ضرورت ہے۔ اور اسے آؤٹ پٹ میں اسٹور کریں اور نیز ہمیں فاصلہ صف عنصر کی کم سے کم اور تعدد کے درمیان کم سے کم قیمت تلاش کرنے اور اسے کم سے کم اسٹور کرنے کی بھی ضرورت ہے۔ یہ تب تک جاری رکھا جائے گا جب تک کہ ہم تمام اقدار کو فاصلے کی صف میں منتقل نہ کریں۔ آخر میں ، ہمارے پاس آؤٹ پٹ میں سب سے موزوں جواب ہے اور ہم اس آؤٹ پٹ ویلیو کو واپس کردیں گے۔

عمل  

C ++ پروگرام دو عناصر کی تعدد کے مابین زیادہ سے زیادہ فرق کے لئے

#include<unordered_map>
#include<iostream>
#include<algorithm>
using namespace std;

int getMaximumDifference(int arr[], int n)
{
    unordered_map<int, int> freq;

    int distance[n];
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (freq.find(arr[i]) == freq.end())
            distance[j++] = arr[i];

        freq[arr[i]]++;
    }
    sort(distance, distance + j);

    int minimum = n+1;

    int output = 0;
    for (int i=0; i<j; i++)
    {
        int currentFrequency = freq[distance[i]];
        output = max(output, currentFrequency - minimum);
        minimum = min(minimum, currentFrequency);
    }

    return output;
}
int main()
{
    int arr[] = {2,4,4,4,3,2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getMaximumDifference(arr, n) << endl;
    return 0;
}
2

دو عناصر کی تعدد کے مابین زیادہ سے زیادہ فرق کے لئے جاوا پروگرام

import java.util.HashMap;
import java.util.Arrays;
class maximumDifferenceFrequency
{
    public static int getMaximumDifference(int arr[], int n)
    {
        HashMap<Integer, Integer> frequency=new HashMap<>();

        int distance[]=new int[n];
        int j = 0;
        for (int i = 0; i < n; i++)
        {
            if (frequency.containsKey(arr[i]))
            {
                frequency.put(arr[i],frequency.get(arr[i])+1);

            }
            else
            {
                frequency.put(arr[i],1);
            }
            distance[j++] = arr[i];
        }
        Arrays.sort(distance);

        int minimum = n+1;

        int output = 0;
        for (int i=0; i<j; i++)
        {
            int currentFrequency = frequency.get(distance[i]);
            output = Math.max(output, currentFrequency - minimum);
            minimum = Math.min(minimum, currentFrequency);
        }

        return output;
    }
    public static void main(String [] args)
    {
        int arr[] = {2,4,4,4,3,2};
        int n = arr.length;

        System.out.println(getMaximumDifference(arr, n));
    }
}
2

دو عناصر کی تعدد کے مابین زیادہ سے زیادہ فرق کے لئے پیچیدگی کا تجزیہ  

وقت کی پیچیدگی

O (n لاگ این) کہاں "این" صف میں عناصر کی تعداد ہے۔

یہ بھی دیکھتے ہیں
ایک صف میں متصل ملحقہ عناصر

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

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔