Xem lại mã Java: Hợp nhất các danh sách được sắp xếp thành một danh sách được sắp xếp duy nhất

Question

Tôi muốn hợp nhất các danh sách được sắp xếp thành một danh sách duy nhất. Làm thế nào là giải pháp này? Tôi tin rằng nó chạy trong thời gian O (n). Bất kỳ sai sót, thiếu hiệu quả hoặc các vấn đề về phong cách rõ ràng?

Tôi không thực sự thích thành ngữ thiết lập cờ cho "đây là lần lặp đầu tiên" và sử dụng nó để đảm bảo "thấp nhất" có giá trị mặc định. Có cách nào tốt hơn không?

public static <T extends Comparable<? super T>> List<T> merge(Set<List<T>> lists) { 
    List<T> result = new ArrayList<T>(); 

    int totalSize = 0; // every element in the set 
    for (List<T> l : lists) { 
     totalSize += l.size(); 
    } 

    boolean first; //awkward 
    List<T> lowest = lists.iterator().next(); // the list with the lowest item to add 

    while (result.size() < totalSize) { // while we still have something to add 
     first = true; 

     for (List<T> l : lists) { 
      if (! l.isEmpty()) { 
       if (first) { 
        lowest = l; 
        first = false; 
       } 
       else if (l.get(0).compareTo(lowest.get(0)) <= 0) { 
        lowest = l; 
       } 
      } 
     } 
     result.add(lowest.get(0)); 
     lowest.remove(0); 
    } 
    return result; 
} 

Lưu ý: đây không phải là bài tập về nhà, nhưng cũng không phải là mã sản xuất.

Answer 1

Giải pháp của bạn có lẽ là giải pháp nhanh nhất. SortedLists có một chi phí chèn log (n), vì vậy bạn sẽ kết thúc với M log (M) (trong đó M là tổng kích thước của các danh sách).

Thêm chúng vào một danh sách và sắp xếp, trong khi dễ đọc hơn, vẫn là nhật ký M (M).

giải pháp của bạn chỉ M.

Bạn có thể dọn dẹp mã của bạn một chút bởi kích thước danh sách kết quả, và bằng cách sử dụng một tham chiếu đến danh sách thấp nhất thay vì một boolean là.

public static <T extends Comparable<? super T>> List<T> merge(Set<List<T>> lists) { 
    int totalSize = 0; // every element in the set 
    for (List<T> l : lists) { 
     totalSize += l.size(); 
    } 

    List<T> result = new ArrayList<T>(totalSize); 

    List<T> lowest; 

    while (result.size() < totalSize) { // while we still have something to add 
     lowest = null; 

     for (List<T> l : lists) { 
      if (! l.isEmpty()) { 
       if (lowest == null) { 
        lowest = l; 
       } else if (l.get(0).compareTo(lowest.get(0)) <= 0) { 
        lowest = l; 
       } 
      } 
     } 

     result.add(lowest.get(0)); 
     lowest.remove(0); 
    } 

    return result; 
} 

Nếu bạn thực sự cụ thể, hãy sử dụng đối tượng Danh sách làm đầu vào và thấp nhất có thể được khởi tạo là lists.get (0) và bạn có thể bỏ qua kiểm tra trống.

Answer 2

Mở rộng trên bình luận Anton của:

Bằng cách đặt các kết quả mới nhất từ ​​mỗi List, cùng với một chỉ số về whch liệt kê nó là, thành một đống, sau đó tiếp tục lấy đầu ra khỏi đống, và đặt một mới mục trên heap từ danh sách thuộc về mục bạn vừa cất cánh.

Ưu tiên của JavaQueue có thể cung cấp việc triển khai heap.

Answer 3

Hiệu quả sẽ hút nếu lists chứa một ArrayList, vì lowest.remove(0) sẽ mất thời gian tuyến tính trong độ dài của danh sách, làm cho thuật toán của bạn O (n^2).

tôi muốn làm:

List<T> result = new ArrayList<T>(); 
for (List<T> list : lists) { 
    result.addAll(list); 
} 
Collections.sort(result); 

đó là trong thời gian O (n log n), và lá đang ít tẻ nhạt để kiểm tra, gỡ lỗi và duy trì.

Answer 4

Vì Balus và meriton đã cùng nhau đưa ra một phản ứng tuyệt vời cho câu hỏi của bạn về thuật toán, tôi sẽ nói sang một bên của bạn về thành ngữ "đầu tiên". Có một số cách tiếp cận khác (như đặt giá trị thấp nhất thành giá trị 'ma thuật'), nhưng tôi cảm thấy rằng "đầu tiên" (mà tôi có thể cho một cái tên dài hơn, nhưng đó là bằng tiếng Anh) là tốt nhất bởi vì nó rất rõ ràng. Sự hiện diện của một boolean như "đầu tiên" là một tín hiệu rõ ràng rằng vòng lặp của bạn sẽ làm một cái gì đó đặc biệt lần đầu tiên thông qua. Nó giúp người đọc.

Tất nhiên bạn không cần nó nếu bạn sử dụng phương pháp Balus/meriton, nhưng đó là một tình huống mà cây trồng lên.

Answer 5

Đây là một câu hỏi thực sự cũ, nhưng tôi không thích bất kỳ câu trả lời nào được gửi, vì vậy đây là những gì tôi đã kết thúc.

Giải pháp chỉ cần thêm tất cả vào một danh sách và sắp xếp là xấu vì độ phức tạp tuyến tính của nhật ký.NẾU điều đó không quan trọng đối với bạn, thì đó chắc chắn là câu trả lời đơn giản và dễ hiểu nhất. Giải pháp ban đầu của bạn không phải là xấu, nhưng đó là một chút lộn xộn, và @ Dathan chỉ ra rằng sự phức tạp là O (m n) cho m danh sách và n tổng số yếu tố. Bạn có thể giảm điều này thành O (n log (m)) bằng cách sử dụng một đống để giảm số lượng so sánh cho mỗi phần tử. Tôi sử dụng một lớp trợ giúp cho phép tôi so sánh các vòng lặp. Bằng cách này tôi không phá hủy các danh sách ban đầu, và nó sẽ hoạt động với độ phức tạp hợp lý bất kể loại danh sách là đầu vào. Lỗ hổng duy nhất tôi thấy với việc thực hiện dưới đây là nó không hỗ trợ danh sách với các yếu tố null, tuy nhiên điều này có thể được sửa nếu muốn.

public static <E extends Comparable<? super E>> List<E> merge(Collection<? extends List<? extends E>> lists) { 
    PriorityQueue<CompIterator<E>> queue = new PriorityQueue<CompIterator<E>>(); 
    for (List<? extends E> list : lists) 
     if (!list.isEmpty()) 
      queue.add(new CompIterator<E>(list.iterator())); 

    List<E> merged = new ArrayList<E>(); 
    while (!queue.isEmpty()) { 
     CompIterator<E> next = queue.remove(); 
     merged.add(next.next()); 
     if (next.hasNext()) 
      queue.add(next); 
    } 
    return merged; 
} 

private static class CompIterator<E extends Comparable<? super E>> implements Iterator<E>, Comparable<CompIterator<E>> { 
    E peekElem; 
    Iterator<? extends E> it; 

    public CompIterator(Iterator<? extends E> it) { 
     this.it = it; 
     if (it.hasNext()) peekElem = it.next(); 
     else peekElem = null; 
    } 

    @Override 
    public boolean hasNext() { 
     return peekElem != null; 
    } 

    @Override 
    public E next() { 
     E ret = peekElem; 
     if (it.hasNext()) peekElem = it.next(); 
     else peekElem = null; 
     return ret; 
    } 

    @Override 
    public void remove() { 
     throw new UnsupportedOperationException(); 
    } 

    @Override 
    public int compareTo(CompIterator<E> o) { 
     if (peekElem == null) return 1; 
     else return peekElem.compareTo(o.peekElem); 
    } 

} 

Mỗi phần tử của danh sách trả về liên quan đến hai thao tác đống O (log), cũng có lần lặp đầu tiên trên tất cả các danh sách. Do đó độ phức tạp tổng thể là O (n log (m) + m) cho n tổng số phần tử và danh sách m. làm cho điều này luôn nhanh hơn nối và sắp xếp.