algorithm - 嵌套循环复杂度

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 

当我循环时，使用 bool 值使用 if current != previous check 快速退出，我正在从列表中删除对象。

它工作正常，但我现在有另一个列表需要匹配，之后可能还有另一个列表。列表的大小不同。

我可以看到的 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 

我想认为我认为第二个更有效但我不确定是正确的。另外，有没有更好的办法？

感谢任何建议/帮助。

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++;
    }
  }
}

这是时间复杂度 O(n)，其中 n 是所有列表长度的总和

---

编辑:如果很难通过 <= 比较键, 那么你可以使用 Set实现代替。添加List1 Set 的 key ，然后遍历其余列表以测试集合成员资格。

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
    }
  }
}