כיצד למצוא את האלמנט הגדול ביותר ב- Java

1. הקדמה

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

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

2. פתרונות

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

2.1. מִיוּן

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

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

  • מיין את המערך בסדר עולה
  • כאלמנט האחרון במערך יהיה האלמנט הגדול ביותר, ה- kהאלמנט הגדול ביותר יהיה ב שישי אינדקס, היכן x = אורך (מערך) - k

כפי שאנו רואים, הפיתרון הוא פשוט אך דורש מיון של כל המערך. לפיכך, מורכבות הזמן תהיה O (n * logn):

public int findKthLargestBySorting (מספר שלם [] arr, int k) {Arrays.sort (arr); int targetIndex = arrllength - k; החזר arr [targetIndex]; }

גישה חלופית היא למיין את המערך בסדר יורד ופשוט להחזיר את האלמנט הלאה (k-1)מדד:

public int findKthLargestBySortingDesc (Integer [] arr, int k) {Arrays.sort (arr, Collections.reverseOrder ()); החזר arr [k-1]; }

2.2. בחירה מהירה

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

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

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

בואו נסתכל על הרעיונות הבסיסיים של אלגוריתם QuickSelect:

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

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

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

בואו נשתמש בפתרון זה:

public int findKthElementByQuickSelect (Integer [] arr, int left, int right, int k) {if (k> = 0 && k k) {return findKthElementByQuickSelect (arr, left, pos - 1, k); } להחזיר findKthElementByQuickSelect (arr, pos + 1, ימין, k - pos + שמאל - 1); } להחזיר 0; }

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

באופן דומה, אלמנטים באינדקסים גבוהים יותר יהיו גדולים מאלמנט הציר:

מחיצת אינטר ציבורי (מספר שלם [] arr, int שמאל, int ימין) {int pivot = arr [ימין]; מספר שלם [] leftArr; מספר שלם [] rightArr; leftArr = IntStream.range (שמאל, ימין). פילטר (i -> arr [i] arr [i]) .boxed () .toArray (Integer [] :: new); rightArr = IntStream.range (שמאל, ימין) .filter (i -> arr [i]> pivot) .map (i -> arr [i]) .boxed () .toArray (Integer [] :: new); int leftArraySize = leftArr.length; System.arraycopy (leftArr, 0, arr, left, leftArraySize); arr [leftArraySize + left] = ציר; System.arraycopy (rightArr, 0, arr, left + leftArraySize + 1, rightArr.length); חזור שמאלה + leftArraySize; }

יש גישה פשוטה ואיטרטיבית להשגת המחיצה:

מחיצת ציבורי אינטרטיבית (שלם [] arr, int שמאל, int ימין) {int pivot = arr [ימין], i = שמאל; עבור (int j = שמאל; j <= ימין - 1; j ++) {אם (arr [j] <= ציר) {החלפה (arr, i, j); i ++; }} החלפה (arr, i, ימין); להחזיר אני; } החלפת חלל ציבורית (שלם [] arr, int n1, int n2) {int temp = arr [n2]; arr [n2] = arr [n1]; arr [n1] = temp; }

פתרון זה עובד עַל) זמן בממוצע. עם זאת, במקרה הגרוע, מורכבות הזמן תהיה O (n ^ 2).

2.3. QuickSelect עם מחיצה אקראית

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

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

במקום להתקשר חֲלוּקָה, אנו קוראים randomPartition השיטה, אשר בוחרת אלמנט אקראי ומחליפה אותו באלמנט הימני ביותר לפני שסוף סוף קוראת ל חֲלוּקָה שיטה.

בואו ליישם את randomPartition שיטה:

Public int randomPartition (שלם arr [], int שמאל, int ימין) {int n = ימין - שמאל + 1; int pivot = (int) (Math.random ()) * n; החלפה (arr, שמאל + ציר, ימין); מחיצת חזרה (arr, שמאל, ימין); }

פתרון זה עובד טוב יותר מהמקרה הקודם ברוב המקרים.

מורכבות הזמן הצפויה של QuickSelect אקראית היא עַל).

עם זאת, מורכבות הזמן הגרועה ביותר עדיין נותרה O (n ^ 2).

3. מסקנה

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

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

כמו תמיד, ניתן למצוא את הקוד השלם לאלגוריתם ב- GitHub.