د صف د دوه سبټونو خورا ممکن ممکنه توپیر


مشکل کچه سخت
په مکرر ډول دننه پوښتل کیږي Atlassian کیډینس هندوستان لارښود وړیا چارج اوپرا پیرو یو Snapchat ټایمز انټرنیټ Xome
پیشه هاش ترتیب کول

فرض کړئ ، موږ یو لرو ضمیمه سور. د ستونزې بیان "د یو سران دوه فرعي اعظمي ممکنه توپیر" څخه غوښتنه کوي ترڅو د صف د دوه فرعي برخو تر مینځ ممکنه ممکنه توپیر ومومي.

شرایط باید تعقیب شی:

  • یو صف کې کولی شي تکرار عناصر ولري ، مګر د عنصر لوړه فریکونسۍ باید له 2 څخه ډیر نه وي.
  • تاسو باید دوه ضمیمې رامینځته کړئ ترڅو د اړونده عناصرو مجموعې ترمینځ توپیر اعظمي وي.
  • د صف ټول عناصر باید د کومو عنصر شاته پاتې کیدو پرته د دوه فرعي برخو تر مینځ ویشل شي.
  • دوه عناصر باید په سبسیټ کې ورته نه وي.

بېلګه

د صف د دوه سبټونو خورا ممکن ممکنه توپیر

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 لري او په هغې کې زیرمه کول subset1.
  4. منفي عنصر او د هغې شمیره په بل نقشه کې زیرمه کړئ.
  5. ټول منفي عناصر اضافه وساتئ چې فریکونسي 1 لري او په هغې کې زیرمه کول subset2.
  6. سبسیټ 1-سبسیټ 2 بیرته وګرځئ.

تشریح

موږ ورکړل سور، موږ اړتیا لرو چې د دوه فرعي برخو عناصرو تر مینځ توپیر ومومو او دا باید اعظمي وي. موږ د نقشه. ځورول د دې پوښتنې حل کولو لپاره یوه مؤثره لار چمتو کوي. موږ به دوه نقشه وکاروو. یو یې په مثبت عناصرو باندې ترسره شوي عملیاتو لپاره دی او بل د منفي عناصرو لپاره. یو صف دواړه کولی شي مثبت او منفي دواړه عناصر ولري ، نو موږ باید دا شیان هم اداره کړو.

موږ به صف او نقشه واخلو. موږ د صفونو هر عنصر غوره کوو او وګورو چې آیا دا له 0 څخه لوی دی. بیا موږ دا په نقشه کې د هغې د پیښو شمیر سره ذخیره کوو. د مثبتو عنصرونو د فریکونسیو ذخیره کولو وروسته موږ د صف په شمول ټول ارزښتونه اضافه کوو چې له 0 څخه ډیر دي او یوازې د 1 فریکوینسي هم لري ، پدې معنی چې موږ اړتیا لرو هغه عناصر له پامه وغورځو چې څو ځله یا له یو څخه ډیر ځله راځي.

ورته کار به د منفي عناصرو سره ترسره شي موږ به د صفونو هر عنصر غوره کړو او دا ځل به وګورو چې ایا دا له 0 څخه کم دی. موږ به دا په نقشه کې ذخیره کړو (دا مثبت شمیره رامینځته کول) د هغې شمیرې سره. پیښې د منفي عناصرو د فریکونسیو ذخیره کولو وروسته ، موږ به د صفونو ټول ارزښتونه اضافه کړو چې له 0 څخه لږ دي او دا چې یوازې د 1 فریکوینسي لري. دلته هم ، موږ اړتیا لرو هغه عناصر نظران کړو چې څو ځله یا ډیر راځي له یو ځل نه

د ټولو مثبتو او منفي عناصرو لنډیز ترلاسه کولو وروسته حالت تعقیب شو چې عناصر یوازې 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

د پیچلتیا تحلیل

د وخت پیچلتیا

اې (N) هلته "n" په صف کې د عناصرو شمیر دی. ځکه چې موږ د هش میپ کارولی دی موږ د دې توان لرو چې په O (1) کې د اضافې / حذف / لټون ترسره کړو.

د ځای پیچلتیا

اې (N) هلته "n" په صف کې د عناصرو شمیر دی.