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

[lina12]

היי,

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

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

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

 

תודה רבה!

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

 

[lina12]

ציטוט של 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