הבדל מקסימלי אפשרי של שתי קבוצות משנה של מערך  


רמת קושי קשה
נשאל לעתים קרובות Atlassian קדנס הודו דירקטי חינם תשלום אופרה PayU Snapchat פעמים באינטרנט קסום
מערך בליל מִיוּן

נניח, יש לנו מספר שלם מערך. משפט הבעיה "הפרש מקסימלי אפשרי של שתי קבוצות משנה של מערך" מבקש לגלות את ההבדל המרבי האפשרי בין שתי קבוצות המשנה של המערך.

התנאים שיש לעקוב אחריהם:

  • מערך יכול להכיל אלמנטים חוזרים, אך התדירות הגבוהה ביותר של אלמנט לא צריכה להיות גדולה מ -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.
ראה גם
קבץ מילים עם אותה סט דמויות

הסבר

נתנו מערך, עלינו לגלות את ההבדל בין סכום האלמנטים של שתי קבוצות משנה וזה צריך להיות מקסימאלי. אנו הולכים להשתמש ב- מַפָּה. חבטות מספק דרך יעילה לפתור שאלה זו. אנו הולכים להשתמש בשתי מפות. האחד נועד לביצוע פעולות על אלמנטים חיוביים ואחר ליסודות השליליים. מערך יכול להכיל אלמנטים חיוביים ושליליים גם יחד, ולכן עלינו להתמודד עם הדבר הזה.

ניקח מערך ומפה. אנחנו הולכים לבחור כל אלמנט במערך ולבדוק אם הוא גדול מ- 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

קוד Java כדי למצוא הבדל מקסימלי אפשרי של שתי קבוצות משנה של מערך

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).

ראה גם
מצא מספרים עם מספר ספרות זוגי של פתרון Leetcode

מורכבות בחלל

O (n) איפה "N" הוא מספר האלמנטים במערך.