从ArrayList中获取匹配的子集

Question

我有一些 POJO 的 ArrayList。比如说员工。

然后我得到另一个ArrayList，其中仅包含该POJO的“id”。（即员工）

现在，我想要一个来自主列表的匹配ID的子列表。

我可以通过迭代主列表并将其与另一个列表的每个 id 进行比较来实现此目的。

但是，我想找出其他最佳解决方案。

任何指示将不胜感激。

Answer 1

编辑：

• 对 Employee 的 ArrayList（或副本）进行排序。运行时间为O(n*log n)
• 查找特定 id 的第一个和最后一个索引。这需要 O(n) 运行时间
• 使用开始和结束索引提取子列表。这也需要 O(n)

总体运行时间：O(n*log n)

以下是整个过程：

初始化 Employee ArrayList：

ArrayList<Employee> empArray = new ArrayList<Employee>();

创建一些随机的员工进行测试：

Employee empTemp = new Employee();
empTemp.setId("1");
empTemp.setName("emp1");
empArray.add(empTemp);

empTemp = new Employee();
empTemp.setId("2");
empTemp.setName("emp2");
empArray.add(empTemp);

empTemp = new Employee();
empTemp.setId("1");
empTemp.setName("emp3");
empArray.add(empTemp);

empTemp = new Employee();
empTemp.setId("4");
empTemp.setName("emp4");
empArray.add(empTemp);

empTemp = new Employee();
empTemp.setId("2");
empTemp.setName("emp5");
empArray.add(empTemp);

根据员工 ID 对员工 ArrayList 进行排序。

Collections.sort(empArray, new Comparator<Object>() {

    public int compare(Object obj0, Object obj1) {
        // TODO Auto-generated method stub
        Employee one = (Employee) obj0; 
        Employee two = (Employee) obj1;
        return one.getId().compareTo(two.getId());
    }
});

初始化一个仅包含员工 ID 的临时字符串 ArrayList：

ArrayList<String> idOnly = new ArrayList<String>();
idOnly.add("1");
idOnly.add("3");

这里我们创建一个新的员工对象，并为其分配我们要为其创建子列表的 id：

empTemp = new Employee();
empTemp.setId(idOnly.get(1));

查找该 ID 的开始和结束索引：

int start = empArray.indexOf(empTemp);
int end = empArray.lastIndexOf(empTemp);

创建一个子列表从开始和结束索引：

List<Employee> temp = null;
if (start != -1 && end != -1){
    temp = empArray.subList(start, end+1);
}

唯一的调整是覆盖 Employee类中的equals(Object obj)：

@Override
public boolean equals(Object obj) {
    // TODO Auto-generated method stub
    Employee two = (Employee) obj; 
    return this.id.equals(two.getId());
}

我知道这有点棘手，但它需要n*日志（n）运行时间。

Answer 2

将 ids 放入 Set 中。然后，您可以迭代您的员工列表并测试它是否在您正在查找的集合中，而不会产生糟糕的 O(n^2) 运行时间。

如果您想编写更漂亮的代码，您还可以查看 Maps.uniqueIndex 为自己构建一个 Map，然后您可以取出来。

Answer 3

无论如何，我必须迭代集合。最佳解决方案是使用一些可以为您完成此操作的库。 Guava 有谓词 在这种情况下这确实很有帮助。检查示例：

//First we build a map that stores Id => Pojo pairs
Map<Integer, POJO> map = Maps.uniqueIndex(yourPojoList, new Function<POJO, Integer>() {
  public Integer apply(POJO pojo) {
    return pojo.getId();
}});
//Now we just intersect both set and your id's list
matchingIds = map.keySet().retainAll(new HashSet(youIdCollection)); //matchingIds is what you need

Answer 4

什么类型有 id 字段？一种方法可能是在第一个 ArrayList 中数组的某个点处插入 POJO，该点等于员工的 id（例如，仅当它是整数时才有效）。

当然，这意味着您可以修改第一个 ArrayList 的插入。否则，循环遍历数组是我知道解决该问题的唯一方法。