שלום אורח התחבר

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

נושאים:יומי

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

arr = [1, 2, 3, 10, 2, 3, 4, 5, 6, 9, 9, 1, 2, 3, 1, 2, 3]

היינו רוצים לזהות שבאינדקס 4 של המערך יש רצף של 5 מספרים עוקבים, והוא הארוך ביותר מבין הרצפים במערך זה.

כשאני רואה כאלה שאלות האינטואיציה הראשונה שלי היא שכדאי להפריד בין הלוגיקה של "איפה יש רצפים" לבין הלוגיקה של חיפוש רצף ארוך ביותר. הראשונה כנראה ספציפית לשאלה ובשביל השניה בטח נוכל להשתמש במנגנונים קיימים של Python. במקרה שלנו אפשר לחשוב על המערך בתור אוסף של רצפים של מספרים עוקבים (חלקם ממש קצרים). במערך שבדוגמא נוכל למצוא את הרצפים הבאים של מספרים עוקבים:

(0, 3)
(3, 1)
(4, 5)
(9, 1)
(10, 1)
(11, 3)
(14, 3)

כל רצף מזוהה על ידי האינדקס בו מתחיל הרצף (המספר הראשון) ואורך הרצף (המספר השני). כך המערך מתחיל באינדקס 0 ברצף של שלושה מספרים עוקבים - המספרים 1, 2 ו-3 ואחריהם באינדקס 3 יש לנו רצף קצר יותר של מספר יחיד הוא המספר 10.

מרגע שזיהיתי שיש פה אוסף של רצפים אני יכול לקודד את הלוגיקה שמחפשת כאלה רצפים לפונקציה מסוג Generator, בואו נקרא לה consecutives. מימוש עשוי להיראות כך:

def consecutives(arr):
    start = 0
    i = start
    while i < len(arr) - 1:
        if arr[i] + 1 == arr[i + 1]:
            i += 1
        else:
            yield(start, i - start + 1)
            start = i + 1
            i = start
    yield(start, i- start + 1)

ואחרי שיש לנו את הפונקציה קל למצוא את כל הרצפים עם לולאת for רגילה:

for seq in consecutives(arr):
    print(seq)

או למצוא את הרצף הכי ארוך עם פונקציית max:

print(max(consecutives(arr), key=lambda s: s[1]))

או למצוא את הרצף שסכום האיברים בו הוא הגדול ביותר (שוב עם max):

print(max(consecutives(arr), key=lambda s: sum(arr[s[0]:s[0]+s[1]])))

והתבנית שכדאי לזכור מכאן - הרבה פעמים שווה לנו להתאמץ לשנות קצת את הבעיה כדי שנוכל לפתור אותה בכלים שאנחנו כבר מכירים.

מעדיפים לקרוא מהטלגרם? בקרו אותנו ב:@tocodeil

או הזינו את כתובת המייל וקבלו את הפוסט היומי בכל בוקר אליכם לתיבה:


נהניתם מהפוסט? מוזמנים לשתף ולהגיב