עזרה באיחוד רשימות מקושרות ממוינות לרשימה ממוינת אחת JAVA - תכנות - HWzone פורומים
עבור לתוכן
  • צור חשבון

עזרה באיחוד רשימות מקושרות ממוינות לרשימה ממוינת אחת JAVA


lina12
 Share

Recommended Posts

היי,

צריך לממש מתודה שמקבלת רשימות מקושרות (מטיפוס גנרי) ומחזירה רשימה ממוינת.

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).

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

 

תודה רבה!

קישור לתוכן
שתף באתרים אחרים

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

 

דבר שני, קוד טיפה יותר אידיומטי יראה בסגנון הזה:

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))

 

קישור לתוכן
שתף באתרים אחרים

ציטוט של 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 וכאלה.

נערך על-ידי lina12
קישור לתוכן
שתף באתרים אחרים

הצטרפ/י לדיון

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

אורח
הוסף תגובה

×   התוכן שהודבק הוא עם עיצוב.   הסר עיצוב

  Only 75 emoji are allowed.

×   הקישור שלך הוטמע אוטומטית.   הצג כקישור רגיל

×   התוכן הקודם שלך שוחזר אוטומטית.   נקה הכל

×   You cannot paste images directly. Upload or insert images from URL.

 Share

×
  • צור חדש...