حداکثر اختلاف ممکن از دو زیر مجموعه یک آرایه  


سطح دشواری سخت
اغلب در Atlassian کادنس هند دیرتی شارژ رایگان اپرا PayU 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 هستند را جمع کرده و در آن ذخیره کنید زیر مجموعه 1.
  4. عنصر منفی و تعداد آن را در نقشه دیگری ذخیره کنید.
  5. تمام عناصر منفی که دارای فرکانس 1 هستند را جمع کرده و در آن ذخیره کنید زیر مجموعه 2.
  6. بازگشت به زیر مجموعه 1-زیرمجموعه 2.

توضیح

ما داده ایم صف، ما باید تفاوت بین جمع عناصر دو زیر مجموعه را پیدا کنیم و این باید حداکثر باشد. ما قصد داریم از a استفاده کنیم نقشه. هشی کردن روشی کارآمد برای حل این سوال فراهم می کند. ما قصد داریم از دو نقشه استفاده کنیم. یکی برای عملیات انجام شده روی عناصر مثبت و دیگری برای عناصر منفی است. یک آرایه می تواند شامل عناصر مثبت و منفی هر دو باشد ، بنابراین ما باید از پس آن چیز برآییم.

همچنین مشاهده کنید
کلمات را با همان مجموعه کاراکترها گروه بندی کنید

ما یک آرایه و نقشه خواهیم گرفت. ما می خواهیم هر یک از عناصر آرایه را انتخاب کنیم و بررسی کنیم که آیا آنها بیشتر از 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

تحلیل پیچیدگی  

پیچیدگی زمان

O (N) جایی که "n" تعداد عناصر آرایه است. از آنجا که ما از HashMap استفاده کرده ایم ، قادر به درج / حذف / جستجو در O (1) هستیم.

همچنین مشاهده کنید
پس از هر پرس و جو برای جایگزینی نویسه ، Palindrome را بررسی کنید

پیچیدگی فضا

O (N) جایی که "n" تعداد عناصر آرایه است.