הייתה לי אתמול שאלה במבחן בג'אווה והייתי רוצה לשמוע את דעתכם על הפיתרון שלי.

השאלה היא בסיבוכיות.

יש לי את המערך הממוין הבא: 1, 2, 3, 4, 6, 7, 8, 9, 12, 20, 21, 22

ואת האובייקט הבא (אני לא זוכר איך הבנאי הלך אבל זה לא ממש משנה פה):

public class Range{
    private int big;
    private int small;
    public int[] arr;


    public int getBig()
    {
        return big;
    }


    public int getSmall()
    {
        return small;
    }
}

מהמערך המקורי נוצר מערך של אובייקטים מסוג Range:

<1, 4>, <6, 9>, <12, 12>, <20, 22>

כאשר לכל איבר במערך יש שדה מקסימום ושדה מינימום למשל האיבר הראשון במערך

<1, 4>

השדה מינימום שלו זה 1 והשדה מקסימום הוא 4.

לאיבר

<12, 12>

השדה מינימום ומקסימום שלו הם 12.

אני צריך לכתוב פונקציה שנקראת

public boolean isSum(Range arr[], int num)

שמקבלת את המערך שלי החדש ומספר מסויים ומחזירה true אם אפשר להגיע למספר ו-false אם לא.

למשל אם אני מקבל את המערך ואת המספר 11 זה מחזיר true כי

3 + 8 = 11

.

הפיתרון שלי:

יצרתי 2 משתנים: min ו-max והכנסתי לשניהם את ערך המספר שאליו אני צריך להגיע.

עכשיו אני רץ בלולאת for על המערך ומחסר מערך ה-min שלי את המספר min שבאובייקט הנוכחי ואותו דבר לגבי ערך ה-max.

עכשיו יש לי 3 אפשרויות:

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

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

3. המספר שאני צריך להוסים נמצא בטווח שבין המספרים באובייקט הנוכחי - אני מחזיר true

דוגמא:

המערך הנתון שלי אני צריך להגיע למספר 20.

min = 20 - 1 = 19

max = 20 - 4 = 16

ממשיך ללופ הבא:

min - 6 = 13

max - 9 = 7

הערכם הבאים הם מינימום 12 ומקסימום 12 ומה שחסר לי זה מספר בין 7 לבין 13 ולכן אני מחזיר true.

בסה"כ סיבוכיות של n.

האם הפיתרון הזה נכון ?

נערך 2014 בפברואר 1111 שנים על-ידי falukky

המערך של האובייקטים מסוג Range נוצר בדרך שרירותית ?

איך הוא נוצר ? (יש <12,12> ולאחריו יש <4,1> וזאת למרות ש 12 מופיע רק פעם יחידה )

לא בדיוק הבנתי את השאלה ..

אתה צריך ש 20 יהיה חיבור של צמד או בכלל של שני ערכים מכלל המערך החדש ?

בהתחלה יש 1 עם 4 וכו' הרי הוא ממוין

ואני צריך ש-20 יהיה חיבור לאו דווקא של צמד