3
여러 개의 정렬 된 목록을 하나의 TreeSet으로 병합하려고합니다. 그런 다음이 TreeSet의 이진 검색 알고리즘을 적용하여 O (log n) 시간 복잡도의 요소를 검색하려고합니다.바이너리 검색을 사용하여 정렬 된 TreeSet에서 요소를 검색하는 방법은 무엇입니까?
아래 코드는 내 코드입니다 있는 내가 duplicacy을 피하기 위해 TreeSet로 내 방법 중 하나에 목록의 목록을 전달하고 결합하고 ... inputs 내부의 모든 목록이 분류되어 있습니다 - 모든
private TreeSet<Integer> tree = new TreeSet<Integer>();
public void mergeMultipleLists(final List<List<Integer>> inputs) {
tree = new TreeSet<Integer>();
for (List<Integer> input : inputs) {
for(Integer ii : input) {
tree.add(ii);
}
}
}
public List<Integer> getItem(final Integer x) {
// extract elements from TreeSet in O(log n)
}
- 첫째, 올바른 방법입니다 여러 개의 정렬 된 목록을 TreeSet으로 병합 하시겠습니까? TreeSet의 여러 정렬 된 목록을 효율적으로 병합하는 직접적인 방법이 있습니까?
- 둘째, O (log n) 시간 복잡도에서 TreeSet의 요소를 어떻게 추출 할 수 있습니까? 요소가
TreeSet에있는 경우x을 찾고 싶으면 거기에있는 경우 반환하고,없는 경우에는TreeSet에서 다음으로 큰 값을 반환하고 싶습니다.
아니면 현재 다른 데이터 구조를 사용하고있는 것이 좋을까요?
업데이트 된 코드 : -
개인 TreeSet의 나무 = 새로운 TreeSet의(); 그것의에 의해
public SearchItem(final List<List<Integer>> inputs) {
tree = new TreeSet<Integer>();
for (List<Integer> input : inputs) {
tree.addAll(input);
}
}
public Integer getItem(final Integer x) {
if(tree.contains(x)) {
return x;
} else {
// now how do I extract next largest
// element from it if x is not present
}
}
각 요소를 개별적으로 추가하는 대신'TreeSet.addAll()'을 사용할 수 있습니다. 그것은 몇 가지 LOC를 구할 것이지만 그것이 더 이상 성능이 있는지 나는 모른다. –
@MikeB :'addAll'에 대한 팁 주셔서 감사합니다 .. 나는 그것을 완전히 잊어 버렸습니다. 그리고 이제 제 두 번째 질문에 관해서 .. 어떤 생각을하고 있습니까? –
여기의 토론과 관련있는 것 같습니다 : http://stackoverflow.com/questions/3390449/computational-complexity-of-treeset-operations-in-java – JLewkovich