1

我有这个火星课程：

public abstract class Martian implements Cloneable {
int id;

public Martian(int id) {
    this.id = id;
}
public Object clone() throws CloneNotSupportedException {
    return super.clone();
}
public int getId() {
    return id;
}
public boolean equals(Object o){
    if( o != null);
    return this.getId() == ((Martian)o).getId();    
}
public abstract void speak();

public String toString(){
    return "Martian" + getId(); 
}       
}

和一个 MartianManager 类：

public class MartianManager {
private ArrayList<Martian> martians;
private ArrayList<Martian> teleporters;

public void addMartian(Martian m) {
    martians.add(m);
    if(m instanceof GreenMartian)
        teleporters.add(m);
}
//public Object clone() {

public Martian getMartianClosestToID(int id) {

}
public void groupSpeak() {
    for(Martian m : martians) {
        m.speak();
    }
}
public void groupTeleport(String dest) {
    for (Martian m : martians){
        if (m instanceof GreenMartian)
            ((GreenMartian) m).teleport(dest);
    }   
}
//public obliterateTeleporters() 

//removeMartian(int id)
}

在MartianManager类中，我有一个方法getMartianClosestToId()返回与输入 id 最接近的 id 火星人。我的问题基本上是在循环中使用什么是最简单的逻辑来做到这一点，或者他们是一种更简单的方法，例如compareTo我不知道比较是否能在这种情况下工作。

4

3 回答 3

1

这不是最简单的，但在很多情况下它会是最快的。

如果您愿意让您的火星人列表始终按 id 排序（如果您不经常添加火星人，这很容易做到，您可以在添加它们时进行排序），您可以这样做：

Comparator<Martian> compareById = new Comparator<Martian>() {
    public int compare(Martian a, Martian b) {
        return Integer.compare(a.getId(), b.getId());
    }
}

然后你可以在你的列表上使用二分搜索来找到它在列表中的位置，如果它被插入的话。

int location = Collections.binarySearch(martians, idToGetClosestTo, compareById);

现在在这一点上，您将拥有它应该去的地方，并且您将拥有以下五个选项之一：

  1. 该位置具有您要查找的 ID。如果是，返回 martians.get(location);
  2. 提供的位置不在列表中，这意味着您正在寻找低于最低或高于最高的位置。2.a. 低于最低：返回最低，martians.get(0)；2.b。高于最高：返回最高，martians.get(martians.length()-1);
  3. 位置高于您要查找的 id。（它不会更低，否则你得到的结果会比你所做的低 1！）所以看看 martians.get(location) 和 martian.get(location - 1) 看看你最接近哪个并返回适当的。

这具有昂贵的前期成本（排序），但是在您对其进行排序之后，您可以使用非常便宜的二进制搜索来每次都非常快速地找到最近的火星人。

如果您要经常添加，那么我建议将新火星人添加到末尾并将您的收藏标记为未排序，然后仅在您即将找到一个时进行排序。

public Martian getMartianClosestToID(int id) {
    if(!martiansAreSorted) Collections.sort(martians,compareById);
    int loc = Collections.binarySearch(martians,id,compareById);
    if(loc >= 0) return martians.get(loc); // found exact match
    // we know loc is negative because it wasn't found - read the docs
    loc = -loc;
    if(loc == 0) return martians.get(0);
    if(loc == martians.size()) return martians.get(loc - 1);
    Martian high = martians.get(loc);
    Martian low = martians.get(loc - 1);

    int highid = high.getId();
    int lowid = low.getId();

    int highdiff = Math.abs(id - highid);
    int lowdiff = Math.abs(id - lowid);

    if(highdiff < lowdiff) return high;
    return low;

}
于 2013-09-19T16:32:24.113 回答
0

像这样的东西应该可以工作。

这是否正是您想要的取决于一些假设。ID 是唯一的吗？火星人能离自己最近吗？如果有两个同样接近的火星人怎么办？还是没有其他火星人？我假设 'id' 参数可能是集合中的 ID 之一 - 而您不想要那个。

但最大的问题是：“最接近”是什么意思？“亲密”的概念通常不适用于 ID。

public Martian getMartianClosestToId(int id) {
    Martian closest = null;
    int leastDist = -1;
    for(Martian m : martians) {
        int mId = m.getId();
        if(mId == id)
             continue; // Skip the Martian with the same id.
        int d = Math.abs(mId - id);
        if(leastDist == -1 || d < leastDist) {
            leastDist = d;
            closest = m;
        }
    }
    return closest;
}

我还没有编译/测试过这个 - 你可能需要修复错别字/错误。

于 2013-09-19T16:12:51.307 回答
0

我认为这比迄今为止的其他答案更简单（OP要求“最简单的逻辑”）：

public Martian getMartianClosestToID(int id)
{
    if (martians == null || martians.isEmpty())
        return null;

    Martian result = martians.get(0);

    for (Martian m : martians)
        if (Math.abs(id - m.getId()) < Math.abs(id - result.getId()))
            result = m;

    return result
}
于 2013-09-19T16:14:06.270 回答