ایک صف کے دو ذیلی سیٹوں کا زیادہ سے زیادہ ممکن فرق  


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

فرض کریں ، ہمارے پاس ایک ہے عددی صف. مسئلہ بیان "ایک سرنی کے دو ذیلی ذخیروں کا زیادہ سے زیادہ ممکنہ فرق" ایک صف کے دو ذیلیوں کے درمیان زیادہ سے زیادہ ممکنہ فرق معلوم کرنے کے لئے کہتا ہے۔

جن شرائط پر عمل کیا جائے:

  • ایک صف میں اعادہ عناصر شامل ہوسکتے ہیں ، لیکن کسی عنصر کی اعلی تعدد 2 سے زیادہ نہیں ہونی چاہئے۔
  • آپ کو دو ذیلی ذخائر بنانا چاہ should تاکہ ان کے متعلقہ عناصر کے جوڑے کے مابین فرق زیادہ سے زیادہ ہو۔
  • صف کے سارے عناصر کو بغیر کسی عنصر کو پیچھے چھوڑ دو دو سبسٹیوں کے درمیان تقسیم کیا جانا چاہئے۔
  • سبسیٹ میں دو عنصر ایک جیسے نہیں ہونے چاہئیں۔

مثال کے طور پر  

ایک صف کے دو ذیلی سیٹوں کا زیادہ سے زیادہ ممکن فرقپن

arr[] = {2, 5, -3, -1, 5, 7}
13

وضاحت

سبسیٹ → (2 ، 7 ، 5) - (-3، -1، 5) = 13

{1, 5, 3, -1, -5, 6}
21

وضاحت

سبسیٹ → (1 ، 3 ، 5 ، 6) - (-5 ، -1) = 21

الگورتھم  

  1. دو اعلان کریں نقشہ جات، ایک مثبت کے لئے اور ایک منفی عنصر کے لئے۔
  2. مثبت نقشے اور ان کی گنتی کو ایک نقشہ میں اسٹور کریں۔
  3. ان تمام مثبت عناصر کو شامل کریں جو تعدد 1 رکھتے ہیں اور اس میں ذخیرہ کرتے رہیں سب سیٹ 1.
  4. منفی عنصر اور اس کی گنتی دوسرے نقشہ میں اسٹور کریں۔
  5. تعدد 1 رکھنے والے تمام منفی عناصر کو شامل کرتے رہیں اور اس میں ذخیرہ کرتے رہیں سب سیٹ 2.
  6. سبسیٹ 1-سبسیٹ 2 واپس کریں۔
یہ بھی دیکھتے ہیں
حروف کی ایک ہی سیٹ کے ساتھ گروپ الفاظ

وضاحت

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

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

اسی چیز کو منفی عناصر کے ساتھ کیا جائے گا ہم کسی صف کے ہر عنصر کو چنیں گے اور اس بار ہم چیک کریں گے کہ یہ 0 سے کم ہے یا نہیں۔ ہم اسے نقشہ میں اسٹور کرنے جارہے ہیں (اسے ایک مثبت تعداد بناتے ہوئے) اس کی تعداد کے ساتھ واقعات منفی عناصر کی تعدد کو اسٹور کرنے کے بعد ، ہم کسی صف کی تمام اقدار کو شامل کرنے جا رہے ہیں جو 0 سے کم ہے اور اس کی فریکوئنسی صرف 1 ہے۔ یہاں بھی ، ہمیں ان عناصر کو نظر انداز کرنے کی ضرورت ہے جو کئی بار یا اس سے زیادہ آئیں گے۔ ایک بار سے

یہ بھی دیکھتے ہیں
ہر کردار کی تبدیلی کے سوال کے بعد Palindrome کی جانچ کریں

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

ضابطے  

کسی سرنی کے دو ذیلی سیٹوں میں زیادہ سے زیادہ ممکنہ فرق تلاش کرنے کے لئے C ++ کوڈ

#include<iostream>
#include<unordered_map>

using namespace std;

int maxDiff(int arr[], int n)
{
    unordered_map<int, int> positiveElement;
    unordered_map<int, int> negativeElement;

    int sumSubset1 = 0, sumSubset2 = 0;
    for (int i = 0; i <= n - 1; i++)
        if (arr[i] > 0)
            positiveElement[arr[i]]++;

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] > 0 && positiveElement[arr[i]] == 1)
            sumSubset1 += arr[i];

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] < 0)
            negativeElement[abs(arr[i])]++;

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] < 0 &&
                negativeElement[abs(arr[i])] == 1)
            sumSubset2 += arr[i];

    return abs(sumSubset1 - sumSubset2);
}
int main()
{
    int arr[] = {2,5,-3,-1,5,7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference found is: " << maxDiff(arr, n);
    return 0;
}
Maximum difference found is: 13

کسی صف کے دو ذیلی سیٹوں میں زیادہ سے زیادہ ممکنہ فرق تلاش کرنے کے لئے جاوا کوڈ

import java.util.HashMap;
class SubsetDifference
{
    public static int getDifference(int arr[], int n)
    {
        HashMap<Integer, Integer> positiveElement=new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> negativeElement=new HashMap<Integer, Integer>();
        int sumSubset1 = 0, sumSubset2 = 0;
        for (int i = 0; i <= n - 1; i++)
        {
            if (arr[i] > 0)
            {
                if(positiveElement.containsKey(arr[i]))
                    positiveElement.put(arr[i],positiveElement.get(arr[i])+1);
                else
                    positiveElement.put(arr[i],1);
            }
        }
        for (int i = 0; i <= n - 1; i++)
            if (arr[i] > 0 && positiveElement.get(arr[i]) == 1)
                sumSubset1 += arr[i];

        for (int i = 0; i <= n - 1; i++)
        {
            if (arr[i] < 0)
            {
                if(negativeElement.containsKey(Math.abs(arr[i])))
                    negativeElement.put(Math.abs(arr[i]),negativeElement.get(Math.abs(arr[i]))+1);
                else
                    negativeElement.put(Math.abs(arr[i]),1);
            }
        }
        for (int i = 0; i <= n - 1; i++)
            if (arr[i] < 0 && negativeElement.get(Math.abs(arr[i]))== 1)
                sumSubset2 += arr[i];

        return Math.abs(sumSubset1 - sumSubset2);
    }
    public static void main(String [] args)
    {
        int arr[] = {2,5,-3,-1,5,7};
        int n = arr.length;
        System.out.println("Maximum difference found is:"+getDifference(arr, n));
    }
}
Maximum difference found is:13

پیچیدگی کا تجزیہ  

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

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔ کیونکہ ہم نے ہش میپ کا استعمال کیا ہے ہم O (1) میں اندراج / حذف / تلاش انجام دینے کے اہل ہیں۔

یہ بھی دیکھتے ہیں
تعداد کی تعداد کے ساتھ نمبر تلاش کریں لیٹ کوڈ حل

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

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