מצא את d הגדול ביותר במערך כך ש- + b + c = d


רמת קושי בינוני
נשאל לעתים קרובות נאמן אמזון בעברית מסירה קנאות פורקיטים FreeCharge
מערך בליל

הצהרת בעיה

נניח שיש לך מערך of מספרים שלמים. ערכי קלט הם כולם אלמנטים מובחנים. הבעיה "מצא את d הגדול ביותר במערך כך ש- + b + c = d" מבקש לגלות את האלמנט הגדול ביותר 'd' בקבוצה כך ש- + b + c = d, כאשר כל האלמנטים שונים זה מזה.

דוגמה

arr[] = {1, 4, 6, 8, 11 }
11

הסבר: שלושת המספרים a, b ו- c הם 1, 4 ו- 6 וסכומם 11.

arr[] = {2,4,6,10,15 }
No such solution exists.

הסבר: מכיוון שאין שלושה מספרים, זה מסתכם במספר.

אַלגוֹרִיתְם

1. Declare a Map.
2. While traversing through the array.
    1. Add and insert the sum of two elements in a map with their indexes in a Map.
3. Set the number to the minimum value of an integer, which we have to find out.
4. Search for the third number in a map by checking the difference of two numbers is present in a map.
5. If true then check if their indexes should not be the same.
6. Check for the maximum of d and the maximum of arr[i] and arr[j] and store it to d.
7. Return d.

הסבר

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

אנו נאחסן את הזוג מכיוון שאנחנו מחפשים d, כך ש- + b + c = d. במקום זאת, אנו נחפש a + b = d - c. כך בהתחלה, כשאנחנו מאחסנים את הזוג ואת המדדים שלהם. נוכל לבדוק את היסוד 'd' כך ש- d קיים במפה. ניתן לעשות זאת על ידי חציית המערך, ואז איסוף שני אלמנטים בבת אחת. בצע את ההבדל בין שני האלמנטים וחפש את ההבדל אם קיים במפה. אם הדבר נמצא נכון, בדוק ששני האלמנטים הנוכחיים לא צריכים להיות באותו אינדקס כמו הזוגות הקודמים באינדקס.

זה הכרחי כדי לבדוק אם לא צריך לחזור על אחד מהאלמנטים באותו אינדקס, ניתן לשקול את המספר החוזר a, b, c ו- d, אך המדדים שלהם, כלומר, המספר עצמו באותו אינדקס צריך להיות לא להיחשב. אז עלינו לבדוק אם מדובר במדדים פלגיאט. כעת עלינו לגלות את המקסימום של arr [i] ו- arr [j] ולבדוק את המקסימום הזה ל- d כדי לגלות את המקסימום ביניהם ולאחסן אותו ל- d. מכיוון שעלינו לגלות את המספר הרביעי d, לכן עלינו למצוא את מקסימום רכיבי המערך, מכיוון ש- d הוא תמיד גדול יותר בין a, b, c ו- d.

יישום

תוכנית C ++ כדי למצוא את d הגדול ביותר במערך כך ש + b + c = d

#include<iostream>
#include<unordered_map>

using namespace std;

int getSumThreeNumber(int arr[], int n)
{
    unordered_map<int, pair<int, int> > MAP;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            MAP[arr[i] + arr[j]] = { i, j };
        }
    }
    int d_number = INT_MIN;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int third = abs(arr[i] - arr[j]);

            if (MAP.find(third) != MAP.end())
            {
                pair<int, int> obj = MAP[third];
                if (obj.first != i && obj.first != j && obj.second != i && obj.second != j)
                    d_number = max(d_number, max(arr[i], arr[j]));
            }
        }
    }
    return d_number;
}
int main()
{
    int arr[] = { 1,4,6,8,11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int res = getSumThreeNumber(arr, n);
    if (res == INT_MIN)
        cout << "No such solution exists";
    else
        cout << res;
    return 0;
}
11

תוכנית Java למצוא את d הגדול ביותר במערך כך ש + b + c = d

import java.util.HashMap;

class CheckIndex
{
    int i, j;

    CheckIndex(int i, int j)
    {
        this.i = i;
        this.j = j;
    }
    int checkI()
    {
        return i;
    }

    int checkJ()
    {
        return j;
    }
}

class sumOfThreeElementToD
{

    public static int getSumThreeNumber(int[] arr, int n)
    {
        HashMap<Integer, CheckIndex> map = new HashMap<>();

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                map.put(arr[i] + arr[j], new CheckIndex(i, j));
            }
        }

        int d_number = Integer.MIN_VALUE;

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                int third = Math.abs(arr[i] - arr[j]);

                if (map.containsKey(third))
                {
                    CheckIndex ci = map.get(third);
                    if (ci.checkI() != i && ci.checkI() != j && ci.checkJ() != i && ci.checkJ() != j)
                    {
                        d_number = Math.max(d_number, Math.max(arr[i], arr[j]));
                    }
                }
            }
        }
        return d_number;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 6, 8, 11 };
        int n = arr.length;
        int output = getSumThreeNumber(arr, n);
        if (output == Integer.MIN_VALUE)
            System.out.println("No such solution exists");
        else
            System.out.println(output);
    }
}
11

ניתוח מורכבות כדי למצוא את d הגדול ביותר במערך כך ש- + b + c = d

מורכבות זמן

O (n2איפה "N" הוא מספר האלמנטים במערך. השגנו מורכבות זו מכיוון שהשתמשנו ב- HashMap המאפשר חיפוש הכנסה ופעולות אחרות בזמן O (1).

מורכבות בחלל

O (n2) איפה "N" הוא מספר האלמנטים במערך. מאז HashMap מאחסן תוספת של זוג אלמנטים שונים של הקלט. בגלל זה, לאלגוריתם יש מורכבות שטח ריבועית.

התייחסות