在ordererd列表中查找最接近的值

I am wondering how you would write a simple java method finding the closet Integer to a given value in a sorted Integer list.

我想知道如何编写一个简单的java方法,在排序的整数列表中找到一个给定值的closet Integer。

Here is my first attempt:

这是我的第一次尝试:

public class Closest {

    private static List<Integer> integers = new ArrayList<Integer>();

    static {
        for (int i = 0; i <= 10; i++) {
            integers.add(Integer.valueOf(i * 10));
        }
    }

    public static void main(String[] args) {

        Integer closest = null;
        Integer arg = Integer.valueOf(args[0]);

        int index = Collections.binarySearch(
                integers, arg);

        if (index < 0) /*arg doesn't exist in integers*/ {
            index = -index - 1;
            if (index == integers.size()) {
                closest = integers.get(index - 1);
            } else if (index == 0) {
                closest = integers.get(0);
            } else {
                int previousDate = integers.get(index - 1);
                int nextDate =  integers.get(index);
                if (arg - previousDate < nextDate - arg) {
                    closest = previousDate;
                } else {
                    closest = nextDate;
                }
            }
        } else /*arg exists in integers*/ {
            closest = integers.get(index);
        }
        System.out.println("The closest Integer to " + arg + " in " + integers
                + " is " + closest);
    }
}

What do you think about this solution ? I am sure there is a cleaner way to do this job ...

您对此解决方案有何看法?我相信有一个更清洁的方式来完成这项工作......

Maybe such method exists somewhere in the Java libraries and I missed it ??

也许这样的方法存在于Java库的某个地方而我错过了?

Manu

9 个解决方案

#1

try this little method:

尝试这个小方法:

public int closest(int of, List<Integer> in) {
    int min = Integer.MAX_VALUE;
    int closest = of;

    for (int v : in) {
        final int diff = Math.abs(v - of);

        if (diff < min) {
            min = diff;
            closest = v;
        }
    }

    return closest;
}

some testcases:

private final static List<Integer> list = Arrays.asList(10, 20, 30, 40, 50);

@Test
public void closestOf21() {
    assertThat(closest(21, list), is(20));
}

@Test
public void closestOf19() {
    assertThat(closest(19, list), is(20));
}

@Test
public void closestOf20() {
    assertThat(closest(20, list), is(20));
}

#2

I think what you have is about the simplest and most efficient way to do it. Finding the "closest" item in a sorted list isn't something that is commonly encountered in programming (you typically look for the one that is bigger, or the one that is smaller). The problem only makes sense for numeric types, so is not very generalizable, and thus it would be unusual to have a library function for it.

我认为你所拥有的是最简单,最有效的方法。在排序列表中查找“最接近”的项目并不是编程中常见的内容(通常会查找较大的项目或较小的项目)。这个问题只对数字类型有意义,所以不是很普遍,因此有一个库函数是不常见的。

#3

To solve the problem, I'd extend the Comparable Interface by a distanceTo method. The implementation of distanceTo returns a double value that represents the intended distance and which is compatible with the result of the compareTo implementation.

为了解决这个问题,我将通过distanceTo方法扩展Comparable Interface。 distanceTo的实现返回一个表示预期距离的double值,它与compareTo实现的结果兼容。

The following example illustrates the idea with just apples. You can exchange diameter by weight, volume or sweetness. The bag will always return the 'closest' apple (most similiar in size, wight or taste)

下面的例子用苹果来说明这个想法。您可以按重量,体积或甜度交换直径。袋子将始终返回'最接近'的苹果(最大的类似,怀疑或味道)

public interface ExtComparable<T> extends Comparable<T> {
   public double distanceTo(T other);
}

public class Apple implements Comparable<Apple> {
   private Double diameter;

   public Apple(double diameter) {
      this.diameter = diameter;
   }

   public double distanceTo(Apple o) {
      return diameter - o.diameter;
   }

   public int compareTo(Apple o) {
      return (int) Math.signum(distanceTo(o));
   }
}

public class AppleBag {
   private List<Apple> bag = new ArrayList<Apple>();

   public addApples(Apple...apples){
      bag.addAll(Arrays.asList(apples));
      Collections.sort(bag);
   }

   public removeApples(Apple...apples){
      bag.removeAll(Arrays.asList(apples));
   }

   public Apple getClosest(Apple apple) {
      Apple closest = null;
      boolean appleIsInBag = bag.contains(apple);
      if (!appleIsInBag) {
         bag.addApples(apple);
      }

      int appleIndex = bag.indexOf(apple);
      if (appleIndex = 0) {
         closest = bag.get(1);
      } else if(appleIndex = bag.size()-1) {
         closest = bag.get(bag.size()-2);
      } else {
         double absDistToPrev = Math.abs(apple.distanceTo(bag.get(appleIndex-1));
         double absDistToNext = Math.abs(apple.distanceTo(bag.get(appleIndex+1));
         closest = bag.get(absDistToNext < absDistToPrev ? next : previous);
      }

      if (!appleIsInBag) {
         bag.removeApples(apple);
      }

      return closest;
   }
}

#4

A solution without binary search (takes advantage of list being sorted):

没有二进制搜索的解决方案(利用列表排序):

public int closest(int value, int[] sorted) {
  if(value < sorted[0])
    return sorted[0];

  int i = 1;
  for( ; i < sorted.length && value > sorted[i] ; i++);

  if(i >= sorted.length)
    return sorted[sorted.length - 1];

  return Math.abs(value - sorted[i]) < Math.abs(value - sorted[i-1]) ?
         sorted[i] : sorted[i-1];
}

#5

Certainly you can simply use a for loop to go through the and keep track of the difference between the value you are on and the value. It would look cleaner, but be much slower.

当然,你可以简单地使用for循环遍历并跟踪你所在的值和值之间的差异。它会看起来更干净,但要慢得多。

See: Finding closest match in collection of numbers

请参阅:在数字集合中查找最接近的匹配项

#6

Not tested

int[] randomArray; // your array you want to find the closest
        int theValue; // value the closest should be near to

        for (int i = 0; i < randomArray.length; i++) {
            int compareValue = randomArray[i];

            randomArray[i] -= theValue;
        }

        int indexOfClosest = 0;
        for (int i = 1; i < randomArray.length; i++) {
            int compareValue = randomArray[i];

            if(Math.abs(randomArray[indexOfClosest] > Math.abs(randomArray[i]){
                indexOfClosest = i;
            }
        }

#7

I think your answer is probably the most efficient way to return a single result.

我认为您的答案可能是返回单个结果的最有效方法。

However, the problem with your approach is that there are 0 (if there is no list), 1, or 2 possible solutions. It's when you have two possible solutions to a function that your problems really start: What if this is not the final answer, but only the first in a series of steps to determine an optimal course of action, and the answer that you didn't return would have provided a better solution? The only correct thing to do would be to consider both answers and compare the results of further processing only at the end.

但是,您的方法存在的问题是0(如果没有列表),1或2个可能的解决方案。当你有一个功能的两个可能的解决方案,你的问题真的开始:如果这不是最终的答案,但只是在一系列步骤中的第一个确定最佳的行动方案,以及你没有的答案怎么办?返回会提供更好的解决方案吗?唯一正确的做法是考虑两个答案并仅在最后比较进一步处理的结果。

Think of the square root function as a somewhat analogous problem to this.

将平方根函数看作是一个有点类似的问题。

#8

If you're not massively concerned on performance (given that the set is searched twice), I think using a Navigable set leads to clearer code:

如果你没有大量关注性能(假设该组被搜索两次),我认为使用Navigable集可以产生更清晰的代码:

public class Closest
{
  private static NavigableSet<Integer> integers = new TreeSet<Integer>();

  static
  {
    for (int i = 0; i <= 10; i++)
    {
      integers.add(Integer.valueOf(i * 10));
    }
  }

  public static void main(String[] args)
  {
    final Integer arg = Integer.valueOf(args[0]);
    final Integer lower = integers.lower(arg);
    final Integer higher = integers.higher(arg);

    final Integer closest;
    if (lower != null)
    {
      if (higher != null)
        closest = (higher - arg > arg - lower) ? lower : higher;
      else
        closest = lower;
    }
    else
      closest = higher;

    System.out.println("The closest Integer to " + arg + " in " + integers + " is " + closest);
  }
}

#9

Your solution appears to be asymptotically optimal. It might be slightly faster (though probably less maintainable) if it used Math.min/max. A good JIT likely has intrinsics that make these fast.

您的解决方案似乎渐近最优。如果它使用Math.min / max,它可能会稍微快一点(尽管可能不太可维护)。一个好的JIT可能具有使这些快速的内在函数。

int index = Collections.binarySearch(integers, arg);
if (index < 0) {
    int previousDate = integers.get(Math.max(0, -index - 2));
    int nextDate = integers.get(Math.min(integers.size() - 1, -index - 1));
    closest = arg - previousDate < nextDate - arg ? previousDate : nextDate;
} else {
    closest = integers.get(index);
}