כיצד למזג שני מערכים ממוינים בג'אווה
1. הקדמה
במדריך זה נלמד כיצד למזג שני מערכים ממוינים למערך ממוין אחד.
2. בעיה
בואו נבין את הבעיה. יש לנו שני מערכים ממוינים ונרצה למזג אותם לאחד.
3. אלגוריתם
כשאנחנו מנתחים את הבעיה, זה די קל לראות שאנו יכולים לפתור בעיה זו באמצעות פעולת המיזוג של מיזוג מיון.
נניח שיש לנו שני מערכים ממוינים foo ו בָּר אורך fooLength ו barLength, בהתאמה. בשלב הבא נוכל להכריז על מערך אחר התמזגה בגודל fooLength + barLength.
עלינו לחצות את שני המערכים באותו לולאה. נשמור על ערך אינדקס נוכחי לכל אחד, fooPosition ו barPosition. על איטרציה נתונה של הלופ שלנו, אנו לוקחים את כל המערך שיש לו את האלמנט בעל הערך הקטן יותר באינדקס שלהם ומקדם את המדד הזה. אלמנט זה יתפוס את המיקום הבא ב- התמזגה מַעֲרָך.
לבסוף, לאחר שהעברנו את כל האלמנטים ממערך אחד, נעתיק את הנותרים מהשני אל ה- התמזגה מַעֲרָך.
עכשיו בואו נראה את התהליך בתמונות כדי להבין טוב יותר את האלגוריתם.
שלב 1:
אנו מתחילים בהשוואה בין האלמנטים בשני המערכים, ואנחנו בוחרים את הקטן יותר.
ואז אנו מגדילים את המיקום ב- ראשון מַעֲרָך.
שלב 2:
כאן אנו מגדילים את המיקום ב שְׁנִיָה מערך ועבר לאלמנט הבא שהוא 8.
שלב 3:
בסוף איטרציה זו, עברנו את כל האלמנטים של ה- ראשון מַעֲרָך.
שלב 4:
בשלב זה אנו פשוט מעתיקים את כל האלמנטים הנותרים מה- שְׁנִיָה מערך ל תוֹצָאָה.
4. יישום
עכשיו בואו נראה איך ליישם את זה:
ציבורי סטטי ציבורי [] מיזוג (int [] foo, int [] סרגל) {int fooLength = foo.length; int barLength = bar.length; int [] מיזוג = int int [fooLength + barLength]; int fooPosition, barPosition, mergedPosition; fooPosition = barPosition = mergedPosition = 0; בעוד (fooPosition <fooLength && barPosition <barLength) {if (foo [fooPosition] <bar [barPosition]) {מיזוג [mergedPosition ++] = foo [fooPosition ++]; } אחר {מיזוג [mergedPosition ++] = סרגל [barPosition ++]; }} בעוד (fooPosition <fooLength) {מיזוג [mergedPosition ++] = foo [fooPosition ++]; } בעוד (barPosition <barLength) {מוזג [mergedPosition ++] = סרגל [barPosition ++]; } להחזיר מיזוג; }ונמשיך בבדיקה קצרה:
@Test הציבור בטל givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray () {int [] foo = {3, 7}; int [] סרגל = {4, 8, 11}; int [] מיזוג = {3, 4, 7, 8, 11}; assertArrayEquals (מיזוג, SortedArrays.merge (foo, bar)); }5. מורכבות
אנו חוצים את שני המערכים ובוחרים את האלמנט הקטן יותר. בסופו של דבר אנו מעתיקים את שאר האלמנטים מה- foo או ה בָּר מַעֲרָך. אז מורכבות הזמן הופכת להיות O (fooLength + barLength). השתמשנו במערך עזר כדי להשיג את התוצאה. אז מורכבות החלל היא גם O (fooLength + barLength).
6. מסקנה
במדריך זה למדנו כיצד למזג שני מערכים ממוינים לאחד.
כרגיל, ניתן למצוא את קוד המקור של הדרכה זו באתר GitHub.
