מצא את המספר הקטן ביותר החסר במערך

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

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

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

2. הסבר לבעיה

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

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

עכשיו, בואו נדמיין מערך אחר: [0, 1, 2, 3]. כמו שהיה 4 אלמנטים, אנו מחפשים מספר שלם בין 0 ו 3. אף אחד לא חסר, ולכן המספר השלם הקטן ביותר שאינו נמצא במערך הוא 4.

3. מערך ממוין

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

בואו ניקח בחשבון את המערך הממוין הבא: [0, 1, 3, 4, 6, 7]. עכשיו, בואו נראה איזה ערך תואם לאיזה אינדקס:

אינדקס: 0 1 2 3 4 5 ערך: 0 1 3 4 6 7

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

מה דעתך ליישם את האלגוריתם הזה ב- Java? בואו ניצור תחילה שיעור SmallestMissingPositiveInteger בשיטה searchInSortedArray ():

מחלקה ציבורית SmallestMissingPositiveInteger {search public intic searchInSortedArray (קלט int []) {// ...}}

כעת נוכל לחזור על המערך ועל חפש את האינדקס הראשון שאינו מכיל את עצמו כערך והחזיר אותו כתוצאה:

עבור (int i = 0; i <input.length; i ++) {if (i! = input [i]) {return i; }}

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

קלט החזרה. אורך;

בואו לבדוק שכל זה עובד כמצופה. דמיין מגוון של מספרים שלמים מ 0 ל 5, עם המספר 3 חָסֵר:

int [] קלט = int int [] {0, 1, 2, 4, 5};

ואז, אם נחפש את המספר השלם החסר הראשון, 3 יש להחזיר:

int result = SmallestMissingPositiveInteger.searchInSortedArray (קלט); assertThat (תוצאה). isEqualTo (3);

אבל, אם נחפש מספר חסר במערך ללא מספר שלם חסר:

int [] קלט = int int [] {0, 1, 2, 3, 4, 5};

נגלה שהמספר השלם החסר הראשון הוא 6, שהוא אורך המערך:

int result = SmallestMissingPositiveInteger.searchInSortedArray (קלט); assertThat (תוצאה) .isEqualTo (input.length);

לאחר מכן נראה כיצד לטפל במערכים לא ממוינים.

4. מערך לא ממוין

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

4.1. מיון מערך הראשון

נתחיל מהפתרון הראשון וניצור חדש searchInUnsortedArraySortingFirst () שיטה.

אז נשתמש שוב באלגוריתם שלנו, אך ראשית עלינו למיין את מערך הקלט שלנו. על מנת לעשות זאת, נשתמש Arrays.sort ():

Arrays.sort (קלט);

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

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

החזר searchInSortedArray (קלט);

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

int [] קלט = int int [] {4, 2, 0, 5};

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

int result = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst (קלט); assertThat (תוצאה). isEqualTo (1);

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

int [] קלט = int int [] {4, 5, 1, 3, 0, 2}; int result = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst (קלט); assertThat (תוצאה) .isEqualTo (input.length);

זהו, האלגוריתם חוזר 6, זהו אורך המערך.

4.2. שימוש במערך בוליאני

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

ראשית, בואו ניצור שיטה שלישית, searchInUnsortedArrayBooleanArray ().

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

בוליאני [] דגלים = בוליאני חדש [input.length]; עבור (int מספר: קלט) {if (number <flags.length) {flags [number] = true; }}

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

עבור (int i = 0; i <flags.length; i ++) {if (! flags [i]) {return i; }} להחזיר דגלים. אורך;

שוב, בואו ננסה את האלגוריתם הזה עם הדוגמאות שלנו. תחילה נשתמש במערך החסר 1 ו 3:

int [] קלט = int int [] {4, 2, 0, 5};

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

int result = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray (קלט); assertThat (תוצאה). isEqualTo (1);

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

int [] input = int int [] {4, 5, 1, 3, 0, 2}; int result = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray (קלט); assertThat (תוצאה) .isEqualTo (input.length);

5. מורכבויות

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

5.1. מערך ממוין

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

5.2. מערך לא ממוין עם אלגוריתם מיון

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

נכון ל- Java 11, ה- Arrays.sort () השיטה משתמשת באלגוריתם מיון מהיר כפול כדי למיין מערכים. המורכבות של אלגוריתם מיון זה היא, באופן כללי, O (n יומן (n)), אם כי זה יכול להתדרדר עד O (n²). זה אומר המורכבות של האלגוריתם שלנו תהיה O (n יומן (n)) באופן כללי ויכול גם להתדרדר עד למורכבות ריבועית של O (n²).

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

5.3. מערך לא ממוין עם מערך בוליאני

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

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

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

6. מסקנה

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

כרגיל, דוגמאות הקוד המלאות המוצגות במאמר זה זמינות באתר GitHub.


$config[zx-auto] not found$config[zx-overlay] not found