lọc ra các yếu tố danh sách với O (n) thời gian phức tạp

Question

Tôi có một danh sách các yếu tố, trong đó mỗi phần tử là một dãy số nguyên không âm. Tôi muốn lọc danh sách theo cách mà chỉ những khoảng cách không bị ràng buộc lớn nhất được tách ra. Và tôi muốn làm điều này theo cách O(n) với vòng lặp đơn. Danh sách này sẽ luôn được sắp xếp theo số nguyên khởi đầu của mỗi dãy. Phần tử phạm vi được bao gồm có thể xảy ra trước hoặc sau phần tử phạm vi kèm theo trong danh sách.

Ví dụ:

Giả danh sách mà tôi có là {[0-12],[5-15],[5-20],[10-20],[11-30],[25-42],[28-40]}. Trong danh sách này, dao động [5-15] và [10-20] sụp đổ trong vòng [5-20] nhiều vì vậy tôi cần phải loại bỏ chúng. Tương tự, yếu tố phạm vi [28-40] bị loại bỏ vì nằm trong phạm vi [25-42]. Tôi muốn thực hiện việc lọc này bằng cách sử dụng một vòng lặp đơn để đạt được độ phức tạp thời gian O(n).

Nó sẽ có thể đạt được điều này? Nếu không, cách tốt nhất để thực hiện lọc với độ phức tạp hơn O(n) là gì. Một giải pháp trong Java sẽ là tuyệt vời.

Answer 1

Phần tử có thể nuốt phần tử trước nếu chúng có cùng khoảng bắt đầu nhưng lớn hơn hoặc bằng nhau. Ngoài ra các yếu tố có thể nuốt tiếp theo nếu phạm vi của một người tiếp theo ít hơn kết thúc của eleemnt hiện tại.

Vì vậy, bạn đi qua danh sách và so sánh các phần tử hiện tại và tiếp theo.

Nếu chúng có currentStart = nextStart và nextEnd> = currentEnd -> xóa hiện tại.

else Nếu nextEnd < = currentEnd -> xóa tiếp theo.

Answer 2

trong giả, thời gian sáp nhập có thể được thực hiện như thế:

def merge(l:list[period], e:period): 
    if l == nil: 
     return list(e) 
    else: 
     lh = l.head 
     ll = l.tail 
     if e.end < lh.start: 
      return e::l // original list prepended with e 
     else if lh.end < e.start: 
      return lh::merge(e,ll) // head + trying to merge period with the tail 
     else: //overlap, make new period from e and list head and merge it with tail 
      newstart = min(e.start, lh.start) 
      newend = max(e.end, lh.end) 
      return merge(period(newstart,newend), ll) 

Trong trường hợp của bạn, bạn phải diff i/o sáp nhập, nhưng ý tưởng tương tự.