Java：在排序列表中查找元素的最佳方法是什么？

发布于 2024-07-15 04:46:36 字数 163 浏览 10 评论 0原文

我有一个

List<Cat>

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

原文

I have a

List<Cat>

sorted by the cats' birthdays. Is there an efficient Java Collections way of finding all the cats that were born on January 24th, 1983? Or, what is a good approach in general?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

猛虎独行 2024-07-22 04:46:36

Collections.binarySearch()< /a>.

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

如果列表很长并且/或者没有多少猫有相同的生日，那么这应该是比直接迭代的重大胜利。

这是我正在考虑的代码。请注意，我假设随机访问列表；对于链表，你几乎陷入了迭代。（感谢 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;

Collections.binarySearch().

Assuming the cats are sorted by birthday, this will give the index of one of the cats with the correct birthday. From there, you can iterate backwards and forwards until you hit one with a different birthday.

If the list is long and/or not many cats share a birthday, this should be a significant win over straight iteration.

Here's the sort of code I'm thinking of. Note that I'm assuming a random-access list; for a linked list, you're pretty much stuck with iteration. (Thanks to fred-o for pointing this out in the comments.)

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;

回复收藏 0 原文

狠疯拽 2024-07-22 04:46:36

二分查找是经典的方法。

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

//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 ];

Binary search is the classic way to go.

Clarification: I said you use binary search. Not a single method specifically. The algorithm is:

//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 ];

回复收藏 0 原文