streamalism.org

1. סקירה כללית

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

2. תיאור טכניקה

בבעיות רבות הכרוכות במערכים או ברשימות, עלינו לנתח כל אלמנט במערך בהשוואה לאלמנטים האחרים שלו.

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

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

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

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

דפוסים נפוצים בגישה של שני מצביעים כוללים:

• שתי עצות המתחילות כל אחת מההתחלה והסוף ועד ששניהם נפגשים
• מצביע אחד נע בקצב איטי ואילו המצביע השני נע בקצב מהיר יותר

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

עכשיו, בואו נסתכל על כמה דוגמאות שיעזרו לנו להבין את הטכניקה הזו קצת יותר טוב.

3. סכום קיים במערך

הבעיה: בהינתן מערך שלם ממוין, עלינו לבדוק האם יש בו שני מספרים כך שסכומם שווה לערך ספציפי.

לדוגמא, אם מערך הקלט שלנו הוא [1, 1, 2, 3, 4, 6, 8, 9] וערך היעד הוא 11ואז השיטה שלנו צריכה לחזור נָכוֹן. עם זאת, אם ערך היעד הוא 20, זה אמור לחזור שֶׁקֶר.

בואו נראה תחילה פיתרון נאיבי:

twoSumSlow (int [] קלט בוליאני ציבורי, int targetValue) {for (int i = 0; i <input.length; i ++) {for (int j = 1; j <input.length; j ++) {if (input [i ] + קלט [j] == targetValue) {return true; }}} להחזיר שקר; }

בפתרון שלעיל, גלגלנו את מערך הקלט פעמיים כדי לקבל את כל השילובים האפשריים. בדקנו את סכום השילוב מול ערך היעד וחזרנו נָכוֹן אם זה תואם. מורכבות הזמן של פתרון זה היא O (n ^ 2) .

בואו נראה כיצד נוכל ליישם את טכניקת הדו-מצביע כאן:

ציבורי בוליאני ציבורי שני (int [], int targetValue) {int pointerOne = 0; pointerTwo = input.length - 1; בעוד (pointerOne <pointerTwo) {int sum = input [pointerOne] + input [pointerTwo]; אם (sum == targetValue) {return true; } אחר אם (סכום <targetValue) {pointerOne ++; } אחר {pointerTwo--; }} להחזיר שקר; }

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

אנו ממשיכים להזיז את המצביעים האלה עד שנקבל את הסכום התואם את ערך היעד או שהגענו לאמצע המערך, ולא נמצאו צירופים. מורכבות הזמן של פתרון זה היא עַל) ומורכבות החלל היא O (1), שיפור משמעותי בהשוואה ליישום הראשון שלנו.

4. סובב מערך k צעדים

בעיה: בהינתן מערך, סובב את המערך ימינה על ידי k מדרגות, היכן k אינו שלילי. לדוגמא, אם מערך הקלט שלנו הוא [1, 2, 3, 4, 5, 6, 7] ו k הוא 4אז הפלט צריך להיות [4, 5, 6, 7, 1, 2, 3].

אנו יכולים לפתור זאת על ידי שוב שתי לולאות אשר יהפכו את הזמן למורכבות O (n ^ 2) או על ידי שימוש במערך נוסף זמני, אך זה יהפוך את המרחב למורכבות עַל).

בואו נפתור זאת באמצעות טכניקת הדו-מצביע במקום:

סיבוב חלל ציבורי (קלט int [], שלב int) {step% = input.length; הפוך (קלט, 0, קלט. אורך - 1); הפוך (קלט, 0, שלב - 1); הפוך (קלט, צעד, קלט. אורך - 1); } הפוך ריק ריק (קלט int [], התחל int, int int) {תוך (start <end) {int temp = input [start]; קלט [התחלה] = קלט [סוף]; קלט [סוף] = temp; התחל ++; סוֹף--; }}

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

באופן ספציפי, ראשית אנו הופכים את כל מרכיבי המערך. ואז, אנו הופכים את הראשון k אלמנטים ואחריהם היפוך שאר האלמנטים. מורכבות הזמן של פתרון זה היא עַל) ו מורכבות החלל היא O (1).

5. אלמנט אמצעי בא רשימה מקושרת

הבעיה: נתון ביחיד רשימה מקושרת, מצא את האלמנט האמצעי שלו. לדוגמא, אם הקלט שלנו רשימה מקושרת הוא 1->2->3->4->5, אז הפלט צריך להיות 3.

אנו יכולים גם להשתמש בטכניקת הדו-מצביע במבני נתונים אחרים הדומים למערכים כמו a רשימה מקושרת:

ציבורי T findMiddle (ראש MyNode) {MyNode slowPointer = ראש; MyNode fastPointer = ראש; ואילו (fastPointer.next! = null && fastPointer.next.next! = null) {fastPointer = fastPointer.next.next; slowPointer = slowPointer.next; } להחזיר slowPointer.data; }

בגישה זו, אנו חוצים את הרשימה המקושרת באמצעות שתי עצות. מצביע אחד מוגבר באחד ואילו השני מגודל בשניים. כאשר המצביע המהיר מגיע לסופו, המצביע האיטי יהיה באמצע הרשימה המקושרת. מורכבות הזמן של פתרון זה היא עַל) ומורכבות החלל היא O (1).

6. מסקנה

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

הקוד במאמר זה זמין באתר Github.