streamalism.org

1. הקדמה

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

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

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

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

2.1. ה קהאלמנט הקטן ביותר

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

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

אנו מקבלים שני מערכים ממוינים (א ו ב), שלא בהכרח צריכים להיות בעלי מספר שווה של אלמנטים:

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

המערך המשולב והממוין לדוגמא שלנו מוצג ב- (c). ה 1 האלמנט הקטן ביותר הוא 3, וה 4 האלמנט הקטן ביותר הוא 20.

2.2. ערכים כפולים

נצטרך גם להגדיר כיצד לטפל בערכים כפולים. אלמנט יכול להופיע יותר מפעם אחת באחד המערכים (אלמנט 3 במערך א) וגם מתרחשים שוב במערך השני (ב).

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

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

3. שתי גישות פשוטות אך פחות יעילות

3.1. הצטרף ואז מיין את שני המערכים

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

int getKthElementSorted (int [] list1, int [] list2, int k) {int length1 = list1.length, length2 = list2.length; int [] combinedArray = int int [length1 + length2]; System.arraycopy (list1, 0, combinedArray, 0, list1.length); System.arraycopy (list2, 0, combinedArray, list1.length, list2.length); Arrays.sort (combinedArray); החזר בשילוב Array [k-1]; }

עם נ בהיותו אורך המערך הראשון ו- m אורכו של המערך השני, אנו מקבלים את האורך המשולב c = n + m.

מכיוון שהמורכבות למיון היא O (c יומן c)המורכבות הכוללת של גישה זו היא O (n יומן n).

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

3.2. למזג את שני המערכים

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

הרעיון הבסיסי של אלגוריתם המיזוג הוא להתחיל בשתי מצביעים, המצביעים על האלמנטים הראשונים של המערך הראשון והשני (א).

לאחר מכן אנו משווים את שני האלמנטים (3 ו 4) בעצות, הוסף את הקטנה יותר (3) לתוצאה, והעביר את המצביע לעמדה אחת קדימה (ב). שוב, אנו משווים את האלמנטים שבמצביעים ומוסיפים את הקטן יותר (4) לתוצאה.

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

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

הנה יישום ב- Java:

סטטי ציבורי int getKthElementMerge (int [] list1, int [] list2, int k) {int i1 = 0, i2 = 0; ואילו (i1 <list1.length && i2 <list2.length && (i1 + i2) <k) {if (list1 [i1] <list2 [i2]) {i1 ++; } אחר {i2 ++; }} אם ((i1 + i2) <k) {return i1 0 && i2> 0) {return Math.max (list1 [i1-1], list2 [i2-1]); } אחר {להחזיר i1 == 0? list2 [i2-1]: list1 [i1-1]; }}

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

4. חיפוש בינארי בשני המערכים

האם נוכל לעשות טוב יותר מ- O (k)? התשובה היא שאנחנו יכולים. הרעיון הבסיסי הוא לעשות אלגוריתם חיפוש בינארי על פני שני המערכים.

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

בואו נגדיר את השלד לשיטה שאנו הולכים ליישם:

int findKthElement (int k, int [] list1, int [] list2) זורק NoSuchElementException, IllegalArgumentException {// קלט בדיקה (ראה להלן) // מטפל במקרים מיוחדים (ראה להלן) // חיפוש בינארי (ראה להלן)}

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

4.1. החיפוש הבינארי

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

בואו נסתכל כיצד ליישם זאת.

4.1.1. מציאת מספר האלמנטים הנכון משני המערכים

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

int nElementsList2 = k - nElementsList1; 

לדוגמא, נניח k = 8. אנו מתחילים בארבעה אלמנטים מהמערך הראשון וארבעה אלמנטים מהמערך השני (א).

אם האלמנט הרביעי במערך הראשון גדול מהאלמנט הרביעי במערך השני, אנו יודעים שלקחנו יותר מדי אלמנטים מהמערך הראשון ויכולים להקטין nElementsList1 (ב). אחרת, אנו יודעים שלקחנו מעט מדי אלמנטים ויכולים להגדיל nElementsList1 (ב ').

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

int ימין = k; int left = = 0; לעשות {nElementsList1 = ((שמאל + ימין) / 2) + 1; nElementsList2 = k - nElementsList1; אם (nElementsList2> 0) {if (list1 [nElementsList1 - 1]> list2 [nElementsList2 - 1]) {right = nElementsList1 - 2; } אחר {left = nElementsList1; }}} תוך (! kthSmallesElementFound (רשימה 1, רשימה 2, nElementsList1, nElementsList2));

4.1.2. עצירת קריטריונים

אנחנו יכולים לעצור בשני מקרים. ראשית, אנו יכולים לעצור אם האלמנט המרבי שאנו לוקחים מהמערך הראשון שווה לאלמנט המרבי שאנו לוקחים מהשני (c). במקרה זה, אנו יכולים פשוט להחזיר את האלמנט הזה.

שנית, אנו יכולים לעצור אם מתקיימים שני התנאים הבאים (ד):

• האלמנט הגדול ביותר שצריך לקחת מהמערך הראשון הוא קטן יותר מהאלמנט הקטן ביותר שאנחנו לא לוקחים מהמערך השני (11 < 100).
• האלמנט הגדול ביותר שצריך לקחת מהמערך השני הוא קטן יותר מהאלמנט הקטן ביותר שאנחנו לא לוקחים מהמערך הראשון (21 < 27).

קל לדמיין (ד ') מדוע מצב זה עובד: כל האלמנטים שאנו לוקחים משני המערכים הם בוודאי קטנים יותר מכל אלמנט אחר בשני המערכים.

הנה הקוד לקריטריונים לעצור:

נמצא בוליאני סטטי פרטיCorrectNumberOfElementsInBothLists (int [] list1, int [] list2, int nElementsList1, int nElementsList2) {// אנחנו לא לוקחים שום אלמנט מהרשימה השנייה אם (nElementsList2 <1) {return true; } אם (list1 [nElementsList1-1] == list2 [nElementsList2-1]) {return true; } אם (nElementsList1 == list1.length) {list list1 [nElementsList1-1] <= list2 [nElementsList2]; } אם (nElementsList2 == list2.length) {list list2 [nElementsList2-1] <= list1 [nElementsList1]; } רשימת החזרה 1 [nElementsList1-1] <= list2 [nElementsList2] && list2 [nElementsList2-1] <= list1 [nElementsList1]; }

4.1.3. ערך ההחזר

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

• אנחנו לא לוקחים שום אלמנטים מהמערך השני, ולכן ערך היעד נמצא במערך הראשון (e)
• ערך היעד נמצא במערך הראשון (e ')
• ערך היעד נמצא במערך השני (e ")

בואו נראה את זה בקוד:

להחזיר nElementsList2 == 0? list1 [nElementsList1-1]: max (list1 [nElementsList1-1], list2 [nElementsList2-1]);

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

4.2. ערכים ראשוניים לגבול שמאל וימין

עד עכשיו, אותנו את הגבול הימני והשמאלי למערך הראשון עם k ו 0:

int ימין = k; int left = 0;

עם זאת, בהתאם לערך של k, אנחנו צריכים להתאים את הגבולות האלה.

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

שנית, אם k גדול ממספר האלמנטים במערך השני, אנו יודעים בוודאות שאנחנו צריכים לקחת לפחות (k - אורך (רשימה 2)) מהמערך הראשון. לדוגמא, נניח k = 7. מכיוון שהמערך השני כולל רק ארבעה אלמנטים, אנו יודעים שצריך לקחת לפחות 3 אלמנטים מהמערך הראשון, כך שנוכל להגדיר ל ל 2:

הנה הקוד לגבולות שמאל וימין מותאמים:

// לתקן את הגבול השמאלי אם k גדול מגודל list2 int left = k <list2.length? 0: k - list2.length - 1; // הגבול הימני הפנימי אינו יכול לחרוג מהרשימה 1 int ימין = min (k-1, list1.length - 1);

4.3. טיפול בתיקים מיוחדים

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

// אנו מחפשים את הערך המינימלי אם (k == 1) {return min (list1 [0], list2 [0]); } // אנו מחפשים את הערך המרבי אם (list1.length + list2.length == k) {return max (list1 [list1.length-1], list2 [list2.length-1]); } // החלף רשימות במידת הצורך כדי לוודא שאנו לוקחים לפחות אלמנט אחד מרשימה 1 אם (k <= list2.length && list2 [k-1] <list1 [0]) {int [] list1_ = list1; list1 = list2; list2 = list1_; }

4.4. אימות קלט

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

• אסור ששני המערכים יהיו כאלה ריק ויש להם לפחות אלמנט אחד
• k חייב להיות >= 0 ולא יכול להיות גדול יותר מאורך שני המערכים יחד

הנה האימות שלנו בקוד:

void checkInput (int k, int [] list1, int [] list2) זורק NoSuchElementException, IllegalArgumentException {if (list1 == null || list2 == null || k list1.length + list2.length) {זרוק NoSuchElementException חדש () ; }}

4.5. קוד מלא

הנה הקוד המלא של האלגוריתם שתיארנו זה עתה:

ציבורי int findKthElement (int k, int [] list1, int [] list2) זורק NoSuchElementException, IllegalArgumentException {checkInput (k, list1, list2); // אנו מחפשים את הערך המינימלי אם (k == 1) {min return (list1 [0], list2 [0]); } // אנו מחפשים את הערך המרבי אם (list1.length + list2.length == k) {return max (list1 [list1.length-1], list2 [list2.length-1]); } // החלף רשימות במידת הצורך כדי לוודא שאנו לוקחים לפחות אלמנט אחד מרשימה 1 אם (k <= list2.length && list2 [k-1] <list1 [0]) {int [] list1_ = list1; list1 = list2; list2 = list1_; } // תקן את הגבול השמאלי אם k גדול מגודל list2 int left = k 0) {if (list1 [nElementsList1 - 1]> list2 [nElementsList2 - 1]) {right = nElementsList1 - 2; } אחר {left = nElementsList1; }}} תוך (! kthSmallesElementFound (רשימה 1, רשימה 2, nElementsList1, nElementsList2)); להחזיר nElementsList2 == 0? list1 [nElementsList1-1]: max (list1 [nElementsList1-1], list2 [nElementsList2-1]); } נמצא בוליאני סטטי פרטי CorrectNumberOfElementsInBothLists (int [] list1, int [] list2, int nElementsList1, int nElementsList2) {// איננו לוקחים שום אלמנט מהרשימה השנייה אם (nElementsList2 <1) {return true; } אם (list1 [nElementsList1-1] == list2 [nElementsList2-1]) {return true; } אם (nElementsList1 == list1.length) {list list1 [nElementsList1-1] <= list2 [nElementsList2]; } אם (nElementsList2 == list2.length) {return list2 [nElementsList2-1] <= list1 [nElementsList1]; } רשימת החזרה 1 [nElementsList1-1] <= list2 [nElementsList2] && list2 [nElementsList2-1] <= list1 [nElementsList1]; }

5. בדיקת האלגוריתם

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

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

int [] sortedRandomIntArrayOfLength (אורך int) {int [] intArray = אקראי חדש (). ints (אורך) .toArray (); Arrays.sort (intArray); להחזיר intArray; }

השיטה הבאה מבצעת בדיקה אחת אחת:

חלל פרטי אקראי () {אקראי אקראי = אקראי חדש (); int length1 = (Math.abs (random.nextInt ()))% 1000 + 1; int length2 = (Math.abs (random.nextInt ()))% 1000 + 1; int [] list1 = sortedRandomIntArrayOfLength (length1); int [] list2 = sortedRandomIntArrayOfLength (length2); int k = (Math.abs (random.nextInt ()) + 1)% (אורך 1 + אורך 2); int result = findKthElement (k, list1, list2); int result2 = getKthElementSorted (רשימה 1, רשימה 2, k); int result3 = getKthElementMerge (רשימה 1, רשימה 2, k); assertEquals (תוצאה 2, תוצאה); assertEquals (result2, result3); }

ואנחנו יכולים לקרוא לשיטה שלעיל להריץ מספר רב של בדיקות כאלה:

@Test בטל randomTests () {IntStream.range (1, 100000) .forEach (i -> אקראי ()); }

6. מסקנה

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

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

כל הקוד במאמר זה זמין באתר GitHub.