중첩 루프 복잡성

Question

다양한 크기의 목록이 여러 개 있습니다. 목록의 각 색인에는 키와 객체가 모두 들어 있습니다. list1.add ('Key', obj).

목록이 모두 정렬됩니다.

내 목표는 목록을 반복하고 목록 2,3,4 또는 n의 1 개 이상의 항목을 키를 사용하여 mainList의 항목과 일치시키는 것입니다. ! 경우 현재 = 이전 검사를 사용하여 신속하게 종료 부울 값을 사용하여 난을 통해 내가 루프로

for i to list1 size 
    for j to list2 size 
    if list1[i] = list2[j] 
     do stuff 

난에서 개체를 삭제하고 있습니다 :

은 현재 내가의 라인을 따라 뭔가를 할 내가 가져가는 목록.

잘 작동하지만 지금은 일치해야하는 다른 목록과 나중에 다른 n 목록을 가질 수 있습니다. 목록의 크기가 다릅니다.

내가 볼 수있는 2 가지 옵션 중 하나는 내부 목록이 변경된 코드의 여러 부분을 반복하는 것입니다.이 방법과는 다릅니다.

다른 옵션은 위의 내용을 확장 한 내부 루프가 완료되면,에 이동하는 것입니다 다음 :

for i to list1 size 
     for j to list2 size 
     if list1[i] = list2[j] 
      do stuff 
     for k to list2 size 
     if list1[i] = list2[k] 
      do stuff 

나는 2가 더 효율적이라고 생각하는 나는 올바른라고 생각하고 싶습니다

그러나 나는 확신 할 수 없다. 더 좋은 방법이 있습니까?

어떤 조언이나 도움을 주셔서 감사합니다.

Answer 1

목록이 모두 정렬 된 경우 각 목록을 한 번만 반복하면됩니다. 주 목록의 각 반복에서 값이 주 목록의 현재 값보다 큰 인덱스를 찾을 때까지 보조 목록 (이전에 저장된 인덱스에서 시작하여 0으로 초기화 됨)을 반복하고이 인덱스를 저장 한 다음 다음 보조 목록

Array<Integer> indices = new Array(n-1); // indices for every list except list1 
for(int i = 0; i < indices.size; i++) { 
    indices[i] = 0; 
} 

for(int i = 0; i < list1.size; i++) { 
    Value curVal = list1[i]; 
    while(indices[0] < list2.size && list2[indices[0]] <= curVal) { 
    if(list2[indices[0]] == curVal) { 
     // do stuff on list2[indices[0]] 
    } 
    indices[0]++; 
    } 
    while(indices[1] < list3.size && list3[indices[1]] < curVal) { 
    if(list3[indices[1]] == curVal) { 
     // do stuff on list3[indices[1]] 
    } 
    indices[1]++; 
    } 
    // etc 
} 

당신은 목록과 현재 인덱스를 포함하는 ListIterator 같은 것을 사용하여 복사 붙여 넣기를 방지 할 수 있습니다

; 다음 메인 루프의 각 반복에 당신은 복사 - 붙여 넣기 코드 블록 대신에 ListIterators의 목록을 반복합니다

public class ListIterator { 
    int index = 0; 
    List<Value> list; 
    Value curVal() { 
    return list[index]; 
    } 
    boolean hasNext() { 
    return (index < list.size); 
    } 
} 

List<ListIterator> iterators; 
for(int i = 0; i < list1.size; i++) { 
    Value curVal = list1[i]; 
    for(int j = 0; j < iterators.size; j++) { 
    ListIterator iterator = iterators[j]; 
    while(iterator.hasNext() && iterator.curVal() <= curVal) { 
     if(iterator.curVal() == curVal) { 
     // do something with iterator.curVal() 
     } 
     iterator.index++; 
    } 
    } 
} 

이 n은의 길이의 합은 시간 복잡도 O (N)입니다 귀하의 목록의 모든

---

편집 :이 <=를 통해 키를 비교하기 어려운 경우에, 당신은 대신 Set 구현을 사용할 수 있습니다. List1 키를 Set에 추가 한 다음 나머지 구성원 목록을 반복하여 집합 구성원을 테스트합니다.

Set<String> set = new Set(List1); 
Array<List> lists = new Array(); 
// add lists to Array<List> 

for(int i = 0; i < lists.size; i++) { 
    List currentList = lists[i]; 
    for(int j = 0; j < currentList.size; j++) { 
    if(set.contains(currentList[j]) { 
     // do something 
    } 
    } 
}