6

我有一个

List<Cat>

按猫的生日排序。是否有一种有效的 Java 集合方法来查找所有出生于 1983 年 1 月 24 日的猫？或者，一般来说什么是好的方法？

4

5 回答 5

9

Collections.binarySearch().

假设猫按生日排序，这将给出其中一只生日正确的猫的索引。从那里，您可以前后迭代，直到找到一个不同生日的人。

如果列表很长和/或没有多少猫共享生日，这应该是直接迭代的重大胜利。

这是我正在考虑的那种代码。请注意，我假设一个随机访问列表；对于链表，你几乎被迭代困住了。（感谢 fred-o 在评论中指出这一点。）

List<Cat> cats = ...; // sorted by birthday
List<Cat> catsWithSameBirthday = new ArrayList<Cat>();
Cat key = new Cat();
key.setBirthday(...);
final int index = Collections.binarySearch(cats, key);
if (index < 0)
    return catsWithSameBirthday;
catsWithSameBirthday.add(cats.get(index));
// go backwards
for (int i = index-1; i > 0; i--) {
    if (cats.get(tmpIndex).getBirthday().equals(key.getBirthday()))
        catsWithSameBirthday.add(cats.get(tmpIndex));
    else
        break;
}
// go forwards
for (int i = index+1; i < cats.size(); i++) {
    if (cats.get(tmpIndex).getBirthday().equals(key.getBirthday()))
        catsWithSameBirthday.add(cats.get(tmpIndex));
    else
        break;
}
return catsWithSameBirthday;
于 2009-03-18T14:06:16.427 回答
8

二进制搜索是经典的方法。

澄清：我说你使用二进制搜索。没有一个具体的方法。算法是：

//pseudocode:

index = binarySearchToFindTheIndex(date);
if (index < 0) 
  // not found

start = index;
for (; start >= 0 && cats[start].date == date; --start);
end = index;
for (; end < cats.length && cats[end].date == date; ++end);

return cats[ start .. end ];
于 2009-03-18T14:06:21.777 回答
3

Google Collections可以通过使用谓词并创建一个过滤集合，其中谓词与日期匹配，来做您想做的事情。

于 2009-03-18T14:18:14.527 回答
1

如果您需要非常快速的搜索，请使用以生日为键的 HashMap。如果您需要对键进行排序，请使用 TreeMap。

因为要允许多只猫的生日相同，所以需要在 Hast/TreeMap 中使用 Collection 作为值，例如

      Map<Date,Collection<Cat>>
于 2009-03-18T14:12:34.617 回答
-1

除非您以某种方式按日期索引集合，否则唯一的方法是遍历所有集合

于 2009-03-18T14:10:40.037 回答