如何从java列表中删除项目 - 通过一组职位？

Question

给定一组职位，Set<Integer> positionsToRemove，我想从列表中删除所有项目，List<?> list，它们的位置对应于集合中的值。

public static void remove(List<?> list, Set<Integer> positionsToRemove) { 
    // ? 
} 

注：

• 列表可能会很长。
• 该集可能很长。
• 小心不要跌破IndexOutOfBounds或ConcurrentModificationException。
• 您可以假定列表和集合不包含空值。

Answer 1

public static void remove(List<?> list, Set<Integer> positionsToRemove) { 
    for (Integer position : positionsToRemove) { 
     list.set((int)position, null); 
    } 
    for (Iterator<?> iterator = list.iterator(); iterator.hasNext();) { 
     Object o = iterator.next(); 
     if (o == null) iterator.remove(); 
    } 
} 

Answer 2

你必须确保在反向删除项目，否则指数将失效。

您可以用List做到这一点很容易：

public static void remove(List<?> list, Set<Integer> positionsToRemove) { 
    final ListIterator<?> iter = list.listIterator(list.size()); 
    while (iter.hasPrevious()) { 
     iter.previous(); 
     if (positionsToRemove.contains(iter.nextIndex())) { 
      iter.remove(); 
     } 
    } 
} 

这需要的，如果ListIterator提供当前索引，也它在反向迭代能力的能力优势。

它也不依赖于“标记值”，因此在输入List中允许输入null。

很明显，你可以做到这一点更简单地用“旧式”索引循环：

public static void remove(List<?> list, Set<Integer> positionsToRemove) { 
    for (int i = list.size() - 1; i >= 0; --i) { 
     if (positionsToRemove.contains(i)) { 
      list.remove(i); 
     } 
    } 
} 

但要注意的是，如果List缺乏RandomAccess这将是O(n^2)，而ListIterator基础的解决办法对于List有O(n)有O(1)remove。

可能更快地返回new List，取决于元素怎么可能要删除，也是List的类型 - 为ArrayList的remove操作是相当昂贵：

public static <T> List<T> remove(List<T> list, Set<Integer> positionsToRemove) { 
    return IntStream.range(0, list.size()) 
      .filter(i -> !positionsToRemove.contains(i)) 
      .mapToObj(list::get) 
      .collect(toList()); 
} 

Answer 3

public static void remove(List<?> list, Set<Integer> positionsToRemove) { 
    int i = 0; 
    for (Iterator<?> iterator = list.iterator(); iterator.hasNext(); ++i) { 
     iterator.next(); 
     if (positionsToRemove.contains(i)) iterator.remove(); 
    } 
}