מציאת אלמנטים K מובילים במערך ג'אווה
1. סקירה כללית
במדריך זה ניישם פתרונות שונים לבעיה של למצוא את k האלמנטים הגדולים ביותר במערך עם Java. כדי לתאר את מורכבות הזמן נשתמש בסימון Big-O.
2. פתרון כוח הברוט
הפתרון הכוח הברוטאלי לבעיה זו הוא חזרו דרך המערך הנתון k פִּי. בכל איטרציה, אנחנומצא את הערך הגדול ביותר. לאחר מכן נסיר ערך זה מהמערך ונכניס לרשימת הפלט:
רשימה ציבורית findTopK (רשימת קלט, int k) {מערך רשימה = ArrayList חדש (קלט); רשימת topKList = ArrayList חדש (); עבור (int i = 0; i <k; i ++) {int maxIndex = 0; עבור (int j = 1; j array.get (maxIndex)) {maxIndex = j; }} topKList.add (array.remove (maxIndex)); } להחזיר topKList; }אם נניח נ להיות בגודל המערך הנתון, מורכבות הזמן של פתרון זה היא O (n * k). יתר על כן, זהו הפיתרון היעיל ביותר.
3. גישת אוספי Java
עם זאת, קיימים פתרונות יעילים יותר לבעיה זו. בחלק זה נסביר שניים מהם באמצעות אוספי Java.
3.1. TreeSet
TreeSet יש עץ אדום-שחורמבנה נתונים כעמוד שדרה. כתוצאה מכך, העלאת ערך לקבוצה זו עולה O (יומן n). TreeSet הוא אוסף ממוין. לכן, אנחנו יכולים שים את כל הערכים ב TreeSetולחלץ את הראשון k שלהם:
רשימה ציבורית findTopK (קלט רשימה, int k) {Set sortedSet = New TreeSet (Comparator.reverseOrder ()); sortedSet.addAll (קלט); החזר sortedSet.stream (). מגבלה (k) .collect (Collectors.toList ()); }ה מורכבות הזמן של פתרון זה היא O (n * log n). מעל לכל זה אמור להיות יעיל יותר מגישת כוח הברוט אם k ≥ יומן n.
חשוב לזכור את זה TreeSet אינו מכיל כפילויות. כתוצאה מכך, הפתרון עובד רק עבור מערך קלט בעל ערכים מובחנים.
3.2. PriorityQueue
PriorityQueue הואערימהמבנה נתונים בג'אווה. בעזרתו, אנחנו יכולים להשיג O (n * log k) פִּתָרוֹן. יתר על כן, זה יהיה פיתרון מהיר יותר מהקודם. בשל הבעיה המוצהרת, k הוא תמיד פחות מגודל המערך. אז זה אומר את זה O (n * log k) ≤ O (n * log n).
האלגוריתם חוזר פעם אחת דרך המערך הנתון. בכל איטרציה, נוסיף אלמנט חדש לערמה. כמו כן, אנו נשמור כי גודל הערימה יהיה קטן או שווה ל- k. אז נצטרך להסיר אלמנטים נוספים מהערמה ולהוסיף חדשים. כתוצאה מכך, לאחר איטרציה דרך המערך, הערימה תכיל את k הערכים הגדולים ביותר:
רשימה ציבורית findTopK (קלט רשימה, int k) {PriorityQueue maxHeap = PriorityQueue חדש (); input.forEach (number -> {maxHeap.add (number); if (maxHeap.size ()> k) {maxHeap.poll ();}}); רשימת topKList = ArrayList חדש (maxHeap); Collections.reverse (topKList); החזר topKList; }4. אלגוריתם בחירה
ישנן גישות רבות לפתרון הבעיה הנתונה. ולמרות שזה מעבר לתחום הדרכה זו, באמצעות גישת אלגוריתם הבחירהיהיה הכי טוב כי זה מניב מורכבות זמן ליניארית.
5. מסקנה
במדריך זה תיארנו כמה פתרונות למציאת ה- k האלמנטים הגדולים במערך.
כרגיל, קוד הדוגמה זמין ב- GitHub.
