Tìm nếu Long (trong danh sách) có thể vừa với Danh sách các giá trị Dài

Question

Tôi có một số List<Long> (A) cho biết kích thước miễn phí có sẵn cho các phân vùng khác nhau. Người dùng đến hỏi với List<Long> (B) cho biết kích thước tệp mà họ muốn lưu trữ.

Bây giờ nếu bất kỳ Long (từ B) có thể phù hợp với bất kỳ kích thước miễn phí trong A, chúng tôi muốn tái sử dụng phân vùng, nếu không tạo phân vùng mới cho chúng.

Làm thế nào tôi có thể biết nếu có giá trị Long từ B có giá trị nhỏ hơn bất kỳ Long trong A.

Nếu tôi sử dụng phương pháp lặp đi lặp lại để quét qua A và tìm hiểu nếu có của B sẽ phù hợp, nó sẽ gây ra thời gian chạy O (n^2), nhưng chúng ta có thể làm tốt hơn không?

Mọi cấu trúc dữ liệu tồn tại cho loại sự cố này?

Answer 1

Dưới đây là một O (n) giải pháp:

Given:

List<Long> A; // size n 
List<Long> B; // size m 

Tìm 2 cạnh:

long a = Collections.max(A); // O(n) 
long b = Collections.min(B); // O(m) 

Sau đó xem nếu A lớn nhất có thể phù hợp với B nhỏ nhất:

boolean canFit = a >= b; // O(1) 

Tổng thời gian độ phức tạp O (n + m) cho n xấp xỉ bằng m là O (n).

Answer 2

Bạn nên xem giao diện NavigableSet. Lưu trữ trong một tập hợp các phân vùng có sẵn với một loại khóa có kích thước. Sau đó, sử dụng toán tử ceiling để tìm phân vùng nhỏ nhất ít nhất bằng một phần mong muốn. NavigableSet cũng hỗ trợ các hoạt động add và remove, tất cả những gì bạn cần để duy trì danh sách phân vùng động.

Thực hiện hợp lý NavigableSet như TreeSet cung cấp hiệu suất O (log n) cho cả ba hoạt động, trong đó n là số lượng phân vùng có sẵn. Khi bạn phân bổ một, bạn sẽ muốn loại bỏ nó và chèn lại mảnh còn lại bằng một khóa nhỏ hơn.

Cách tiếp cận khác là sử dụng một loạt các nhóm có kích thước lôgarit. Đây là những gì malloc giống như cấp phát bộ nhớ có xu hướng làm. Chúng sẽ không khớp các yêu cầu kích thước cho các khối có sẵn một cách chính xác như cách tiếp cận ở trên, nhưng chúng sẽ rất gần với thời gian không đổi. Xem phần thảo luận here để biết ví dụ về chi tiết.