אוקי, אז השאלה היא כזו –
נתון מערך של מספרים ומספר כלשהו k.
צריך לכתוב אלגוריתם שמוצא את הרצף הכי ארוך במערך שיש בו בדיוק k מספרים שונים זה מזה נתון לי ש-k<=n.
קודם כל להיות בטוח שאני סגורה על השאלה.
צריך למצוא את הרצף הכי ארוך שיש בו k מספרים שונים – זאת אומרת שאם k=1, צריך למצוא את הרצף הכי ארוך של מספר מסוים שחוזר על עצמו. אם k=2 צריך למצוא את הרצף הכי ארוך של שני מספרים שחוזרים על עצמם וכן הלאה.
אני אתחיל מכמה דוגמאות קטנות –
arr = [1,5,3,100,3, 2, 2] k=1 longest_k_unique = [2,2] k=2 longest_k_unique = [3,100,3] k=3 longest_k_unique = [3,100,3,2,2]
אוקי, אחלה, נראה די פשוט.
אז איזה אלגוריתם יכול למצוא את הרצף הזה?
אני אתחיל מהאלגוריתם הנאיבי בעל הסיבוכיות הגרועה –
כדי למצוא את הרצף הארוך ביותר אפשר להריץ שתי לולאות אחת בתוך השנייה – הלולאה הפנימית תספור את כל המספרים השונים בין כל שני אינדקסים, ותשמור את הרצף הארוך ביותר.
הפתרון הזה עובד כי הוא בעצם עובר על כל הרצפים האפשריים – מכל אינדקס לכל אינדקס, ובודק האם הם הרצף הארוך ביותר.
אני אכתוב מהר את הפתרון הנאיבי שלי –
def find_longest_k_unique(arr, k):
longest_k_uniuqe = []
for i in range(0,len(arr)):
current_k_unique = []
unique_count = 0
for j in range(i,len(arr)):
current_k_unique.append(arr[j])
if arr[j] not in current_k_unique:
unique_count += 1
if unique_count == k:
break
if len(current_k_unique) > len(longest_k_uniuqe):
longest_k_uniuqe = deepcopy(current_k_unique)
return longest_k_uniuqe
מה הסיבוכיות של הפתרון הזה? ובכן, יש כמה אופטימיזציות שאפשר לעשות כדי לשפר את האלגוריתם הזה, אבל בגדול הוא ישאר בסיבוכיות של (O(N2 (כרגע הוא בסיבוכיות עוד יותר איומה של (O(N3 כי החיפוש שלי של מספרים ברצף הנוכחי גם הוא בסיבוכיות (O(N, אבל זה משהו שאפשר לתקן בקלות).
נראה לי שאני יכולה לשפר את הסיבוכיות של הפתרון הזה. האינטואיציה שלי אומרת משהו כזה – במקום לעבור כל פעם על כל רצף בנפרד, אפשר להתחיל מרצף מסוים, ואז להרחיב אותו ולהקטין אותו בהתאם עד שמוצאים את הרצף האידיאלי.
איך אני עושה את זה?
אני אכתוב אלגוריתם שמתחיל משני אינדקסים – i,j במיקומים 0 ו-1 בהתאמה.
אני אתחזק unique_count שהוא משתנה המכיל את מספר ה-unique-ים ברצף הנוכחי שלי. כל פעם ש-unique_count יגיע ל-k אני אשמור את הרצף הנוכחי ואנסה להרחיב אותו ימינה (לכיוון סוף המערך), כל פעם ש-unique_count יעבור את ה-k אני אקטין את הרצף הנוכחי שלי מהכיוון השמאלי.
בשיטה הזו אני אעבור על כל הרצפים – כל אחד מהאינדקסים i ו-j יעבור על כל האינדקסים במערך – אבל אני אעבור כל אינדקס פעמיים בלבד, ולא n פעמים, ולכן הסיבוכיות שלי תהיה לינארית.
אני אכתוב את האלגוריתם הזה ואראה אם הוא עובד.
def find_longest_k_unique(arr, k):
longest_k_uniuqe = []
if len(arr) == 1:
return arr
else:
i=0
j=1
current_k_unique = [arr[i],arr[j]]
current_range = defaultdict(int)
current_range[arr[i]] += 1
current_range[arr[j]] += 1
while j len(longest_k_uniuqe):
longest_k_uniuqe = deepcopy(current_k_unique)
if unique_count <= k:
j += 1
current_k_unique.append(arr[j])
current_range[arr[j]] += 1
else:
del current_k_unique[0]
current_range[arr[i]] -= 1
i += 1
return longest_k_uniuqe
אוקי, יש אלגוריתם, אני אריץ בדיקה על אחת הדוגמאות למעלה –
find_longest_k_unique([1,5,3,100,3, 2, 2], 2):
longest_k_uniuqe = []
i=0
j=1
current_k_unique = [1,5]
current_range = {1:1,5:1}
unique_count = 2
len([1,5]) > len([]) → longest_k_uniuqe = [1,5]
j=2
current_k_unique = [1,5,3]
current_range = {1:1,5:1,3:1}
unique_count = 3
אוי, רגע, קלטתי פה באג קטן אבל משמעותי.
בשורה הזו –
unique_count = sum(current_range.values())
אני סוכמת את מספר החזרות של כל הערכים ברצף, ולא את מספר הערכים השונים. מספר הערכים השונים זה בעצם ה-keys.
אבל זה מוביל אותי לשאלה – למה רציתי לספור כמה פעמים כל מספר חוזר? אני לא משתמשת במספר הזה, המטריקה החשובה שלי היא כמה מספרים שונים יש.
אני אשנה את הקוד בהתאם –
def find_longest_k_unique(arr, k):
longest_k_uniuqe = []
if len(arr) == 1:
return arr
else:
i=0
j=1
current_k_unique = [arr[i],arr[j]]
uniques_in_range = set()
uniques_in_range.add(arr[i])
uniques_in_range.add(arr[j])
while j len(longest_k_uniuqe):
longest_k_uniuqe = deepcopy(current_k_unique)
if unique_count <= k:
j += 1
current_k_unique.append(arr[j])
uniques_in_range.add(arr[j]
else:
del current_k_unique[0]
uniques_in_range.remove(arr[i]
i += 1
return longest_k_uniuqe
אוקי, אני אתחיל להריץ את הדוגמא שלי מחדש.
find_longest_k_unique([1,5,3,100,3, 2, 2], 2):
longest_k_uniuqe = []
i=0
j=1
current_k_unique = [1,5]
uniques_in_range = {1,5}
unique_count = 2 = k
len([1,5]) > len([]) → longest_k_uniuqe = [1,5]
j=2
current_k_unique = [1,5,3]
uniques_in_range = {1,5,3}
unique_count = 3 > k
current_k_unique = [5,3]
uniques_in_range = {5,3}
i=1
unique_count = 2 = k
j=3
current_k_unique = [5,3,100]
uniques_in_range = {5,3,100}
unique_count = 3 > k
current_k_unique = [3,100]
uniques_in_range = {3,100}
i=2
unique_count = 2 = k
j=4
current_k_unique = [3,100,3]
uniques_in_range = {3,100}
unique_count = 2 = k
len([3,100,3]) > len([1,5]) → longest_k_uniuqe = [3,100,3]
j=5
current_k_unique = [3,100,3,2]
uniques_in_range = {3,100,2}
unique_count = 3 > k
current_k_unique = [100,3,2]
uniques_in_range = {100,2}
i=2
אוקי… טוב, זה היה מסע ארוך כדי להגיע לנקודה שבה הבנתי למה הייתי צריכה לספור את החזרות של כל מספר שונה – אמנם זה לא משנה לי כמה פעמים מספר חוזר ברצף שלי, אבל אני צריכה לדעת מתי הוא מתאפס, למשל במקרה שהגעתי אליו עכשיו הוצאתי את 3 מה- uniques_in_range שלי למרות שהוא עדיין קיים ברצף.
אז אני אחזור לפתרון המקורי עם תיקון –
def find_longest_k_unique(arr, k):
longest_k_uniuqe = []
if len(arr) == 1:
return arr
else:
i=j=0
current_k_unique = [arr[i]]
current_range = defaultdict(int)
current_range[arr[i]] += 1
while j len(longest_k_uniuqe):
longest_k_uniuqe = deepcopy(current_k_unique)
if unique_count <= k:
j += 1
current_k_unique.append(arr[j])
current_range[arr[j]] += 1
else:
del current_k_unique[0]
current_range[arr[i]] -= 1
if current_range[arr[i]] == 0:
current_range.pop(arr[i])
i += 1
return longest_k_uniuqe
עכשיו – כדי לספור את מספר הספרות השונות שיש לי ברצף אני בודקת כמה ערכים שונים יש לי בטבלת ה-current_range שלי – כך אני סופרת כמה ספרות יש לי שמופיעות לפחות פעם אחת ברצף.
אם אחרי שאני מורידה ספרה מתחילת הרצף מספר החזרות שלה מתאפס, היא מוסרת מהטבלה ואז אני לא אספור אותה.
*כמו כן, הכנסתי שינוי שכבר הרבה זמן נראה לי הגיוני – במקום להתחיל את i ו-j משני אינדקסים שונים אני מתחילה אותם באותו אינדקס וככה חוסכת קצת כתיבת קוד.
אני אחזור לדוגמא שלי –
find_longest_k_unique([1,5,3,100,3, 2, 2], 2):
longest_k_uniuqe = []
i=j=0
current_k_unique = [1]
current_range = {1:1}
unique_count = 1
j=1
current_k_unique = [1,5]
current_range = {1:1,5:1}
unique_count = 2
len([1,5]) > len([]) → longest_k_uniuqe = [1,5]
j=2
current_k_unique = [1,5,3]
current_range = {1:1,5:1,3:1}
unique_count = 3
i=1
current_k_unique = [5,3]
current_range = {5:1,3:1}
unique_count = 2
j=3
current_k_unique = [5,3,100]
current_range = {5:1,3:1,100:1}
unique_count = 3
i=2
current_k_unique = [3,100]
current_range = {3:1,100:1}
unique_count = 2
j=4
current_k_unique = [3,100,3]
current_range = {3:2,100:2}
unique_count = 2
len([3,100,3]) > len([1,5]) → longest_k_uniuqe = [3,100,3]
j=5
current_k_unique = [3,100,3,2]
current_range = {3:2,100:2,2:1}
unique_count = 3
i=3
current_k_unique = [100,3,2]
current_range = {3:1,100:2,2:1}
unique_count = 3
i=2
current_k_unique = [3,2]
current_range = {100:2,2:1}
unique_count = 2
j=6
current_k_unique = [3,2,2]
current_range = {100:2,2:2}
return [3,100,3]
סבבה, קיבלתי את התוצאה הנכונה, אבל עליתי פה על באג קטן בדרך – אני לא נכנסת ללולאה האחרונה אחרי שהעליתי את j באחד והוספתי לרצף, אז צריך או להחליף את הסדר של הדברים או להכניס תנאי אחר.
אם אני קודם אבדוק את התנאי שמוסיף איברים לרצף, ורק אחר כך אבדוק את התנאי שמשווה לאורך של הרשימה הארוכה ביותר, הפעם הראשונה שאני אשווה לרשימה הארוכה ביותר תהיה כבר אחרי הכנסה אחת של איבר לרצף, ואני אפספס את הרצף הראשון שהוא באורך 1 (מאותו רגע הלולאה תסתדר להמשך).
כיוון שרצף באורך 1 זה פשוט תא אחד ואין לי בעיה לקבל תא אחד בכל מקום אחר במערך (ואני מכסה את מקרה הקצה של מערך באורך 1 בלבד אז אני מרגישה בנוח עם זה. אם היה חשוב לי לקבל את הרצף הראשון הייתי מוסיפה טיפול מחוץ ללולאה.
def find_longest_k_unique(arr, k):
longest_k_uniuqe = []
if len(arr) == 1:
return arr
else:
i=j=0
current_k_unique = [arr[i]]
current_range = defaultdict(int)
current_range[arr[i]] += 1
unique_count = len(current_range.keys())
while j < len(arr)-1:
if unique_count len(longest_k_uniuqe):
longest_k_uniuqe = deepcopy(current_k_unique)
return longest_k_uniuqe
אני אבדוק הפעם על דוגמא יותר קצרה כי אני כבר די בטוחה באלגוריתם ולגמרי נמאס לי מהבדיקה הארוכה הזו.
find_longest_k_unique([1,1, 3], 2):
longest_k_uniuqe = []
i=j=0
current_k_unique = [1]
current_range = {1:1}
unique_count = 1
j=1
current_k_unique = [1,1]
current_range = {1:2}
unique_count = 1
j=2
current_k_unique = [1,1,3]
current_range = {1:2,3:1}
unique_count = 2
len([1,1,3]) > len([]) → longest_k_uniuqe=[1,1,3]
return [1,1,3]
נראה טוב.
כמו שכבר אמרתי, הסיבוכיות היא לינארית, כיוון שאני לא יודעת שום דבר על המערך (הוא לא ממויין או משהו כזה), אני לא אוכל להגיע לסיבוכיות טובה יותר – נראה לי שהגיע הזמן לקודד.
קוד בגיט –
https://github.com/mgershovitz/maya_solves/blob/master/longest_k_unique.py
