lina12 פורסם 2021 באפריל 21 Share פורסם 2021 באפריל 21 היי, צריך לממש מתודה שמקבלת רשימות מקושרות (מטיפוס גנרי) ומחזירה רשימה ממוינת. public static <T extends Comparable<T>> List<T> combineSorted(LinkedList<T> ... lists){ int listsLength = lists.length; //number of lists int length = lists[0].size(); //elements on each list List<T> newList = new LinkedList<T>(); for(int i = 0; i < listsLength; i++) { for(int j = 0; j < length; j++) { newList.add(lists[i].get(j)); } } Collections.sort(newList); return newList; הקוד עובד אבל אשמח לעזרה עם חישוב הסיבוכיות (יש k רשימות מקושרות וכל אחת מהרשימות היא באורך N). ובמידה ויש רעיון למישהו לקוד עם סיבוכיות טובה יותר אשמח לשמוע גם. תודה רבה! ציטוט קישור לתוכן שתף באתרים אחרים More sharing options...
af db creid פורסם 2021 באפריל 21 Share פורסם 2021 באפריל 21 קודם כל, הקוד לא יעבוד עם כמה רשימות מקושרות באורך שונה. דבר שני, קוד טיפה יותר אידיומטי יראה בסגנון הזה: public static <T extends Comparable<T>> List<T> combineSorted(LinkedList<T> ... lists) { List<T> newList = new LinkedList<T>(); for (LinkedList<T> list : lists) { newList.addAll(list); } Collections.sort(newList); return newList; } אבל הקוד הכי פשוט הוא עם Java 8 Streams API: public static <T extends Comparable<T>> List<T> combineSorted(LinkedList<T> ...lists) { return Arrays.stream(lists) .flatMap(List::stream) .sorted() .collect(Collectors.toList()); } ולגבי הסיבוכיות: אנחנו מוסיפים כל רשימה לרשימה הסופית. K רשימות, כל אחת N איברים - סה"כ KN. חוץ מזה, אנחנו ממיינים את הרשימה הזו. Collections.sort() מעתיק את הרשימה למערך (O(len)), ואז ממיין אותו בTimSort (שזה O(len*log(len))), ובסוף מעתיק בחזרה לרשימה (שוב O(len)). len שלנו הוא K*N, אז סה"כ הסיבוכיות היא: O(K*N + K*N + K*N*log(K*N) + K*N) = O(K*N*log(K*N)) ציטוט קישור לתוכן שתף באתרים אחרים More sharing options...
lina12 פורסם 2021 באפריל 22 מחבר Share פורסם 2021 באפריל 22 (נערך) ציטוט של af db creid קודם כל, הקוד לא יעבוד עם כמה רשימות מקושרות באורך שונה. דבר שני, קוד טיפה יותר אידיומטי יראה בסגנון הזה: public static <T extends Comparable<T>> List<T> combineSorted(LinkedList<T> ... lists) { List<T> newList = new LinkedList<T>(); for (LinkedList<T> list : lists) { newList.addAll(list); } Collections.sort(newList); return newList; } אבל הקוד הכי פשוט הוא עם Java 8 Streams API: public static <T extends Comparable<T>> List<T> combineSorted(LinkedList<T> ...lists) { return Arrays.stream(lists) .flatMap(List::stream) .sorted() .collect(Collectors.toList()); } ולגבי הסיבוכיות: אנחנו מוסיפים כל רשימה לרשימה הסופית. K רשימות, כל אחת N איברים - סה"כ KN. חוץ מזה, אנחנו ממיינים את הרשימה הזו. Collections.sort() מעתיק את הרשימה למערך (O(len)), ואז ממיין אותו בTimSort (שזה O(len*log(len))), ובסוף מעתיק בחזרה לרשימה (שוב O(len)). len שלנו הוא K*N, אז סה"כ הסיבוכיות היא: O(K*N + K*N + K*N*log(K*N) + K*N) = O(K*N*log(K*N)) נתון בתרגיל שכל הרשימות שהמתודה מקבלת הן באורך זהה (N). השאלה שלי היא אם לא צריך להתייחס לעובדה שזה רשימות מקושרות וליצור מחלקה של Node וכאלה. נערך 2021 באפריל 22 על-ידי lina12 ציטוט קישור לתוכן שתף באתרים אחרים More sharing options...
Recommended Posts
הצטרפ/י לדיון
בשלב זה תוכל/י להצטרף לדיון, ולאחר מכן להצטרף לקהילה שלנו. אם כבר יש לך חשבון אצלנו, אנא התחבר/י עכשיו על מנת להגיב תחת שם המשתמש שלך.
לתשומת לבך: התגובה תופיע לגולשים לאחר אישור של צוות הנהלת הפורומים.