代码之家 › 专栏 › 技术社区 › john

通过与一个条目进行比较来查找列表中最近的条目

data-structures sorting algorithm java

john · 技术社区 · 5 年前

我有一个 Unit 类中有许多字段,如下所示:

public class Unit {
  private final int id;
  private final int beds;
  private final String city;
  private final double lat;
  private final double lon;

  // constructors and getters here
  // toString method

}

我现在有一个清单 单位 这是一个 List 包含许多单位的对象。现在我需要找到最近的单位 列表 反对 Unit x . 限制结果。

  private List<Unit> nearestUnits(List<Unit> lists, Unit x, int limit) {
    List<Unit> output = new ArrayList<>();

    // how do I sort lists object in such a way so that I can get nearest units here to "x"?

    return output;
  }

我们有一份长期的礼物 单位 类,以便我们可以使用它计算欧几里德距离并进行比较。我对如何按最短距离对单位列表进行排序并获取最近的单位感到困惑。我现在正在使用Java 7,所以不能使用Java 8。

0 回复 | 直到 5 年前

Abra BlueJK 5 年前

你说你知道如何计算距离,所以我下面的代码不包括计算,所以我假设你可以实现 calculateDistance() 方法。我用一个 TreeMap 自动排序添加到其中的条目和类 Double 工具 Comparable 所以你不需要处理分类。这个 Iterator 将返回按计算距离排序的键。

private List<Unit> nearestUnits(List<Unit> lists, Unit x, int limit) {
    TreeMap<Double, Unit> sorted = new TreeMap<>();
    List<Unit> output = new ArrayList<>();
    for (Unit unit : lists) {
        Double distance = calculateDistance(unit, x);
        sorted.put(distance, unit);
    }
    Set<Double> keys = sorted.keySet();
    Iterator<Double> iter = keys.iterator();
    int count = 0;
    while (iter.hasNext() && count < limit) {
        Double key = iter.next();
        Unit val = sorted.get(key);
        output.add(val);
        count++;
    }
    return output;
}

Dongkwon Lee 5 年前

//此距离方法引用自 https://stackoverflow.com/a/16794680/6138660

public static double distance(double lat1, double lat2, double lon1,
        double lon2) {
    final int R = 6371; // Radius of the earth

    double latDistance = Math.toRadians(lat2 - lat1);
    double lonDistance = Math.toRadians(lon2 - lon1);
    double a = Math.sin(latDistance / 2) * Math.sin(latDistance / 2)
            + Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2))
            * Math.sin(lonDistance / 2) * Math.sin(lonDistance / 2);
    double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
    double distance = R * c * 1000; // convert to meters

    distance = Math.pow(distance, 2);

    return Math.sqrt(distance);
}

private List<Unit> nearestUnits(List<Unit> lists, Unit x, int limit) {


    lists.sort(new Comparator<Unit>() {

        @Override
        public int compare(Unit o1, Unit o2) {

            double flagLat = x.getLat();
            double flagLon = x.getLon();

            double o1DistanceFromFlag = distance(flagLat, o1.getLat(), flagLon, o1.getLon());
            double o2DistanceFromFlag = distance(flagLat, o2.getLat(), flagLon, o2.getLon());

            return Double.compare(o1DistanceFromFlag, o2DistanceFromFlag);
        }
    });

    return lists.subList(0, limit);;
  }