Java 在有序列表中查找最接近的值
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1187352/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find closest value in an ordered list
提问by Manuel Selva
I am wondering how you would write a simple java method finding the closest Integer to a given value in a sorted Integer list.
我想知道如何编写一个简单的 java 方法，在排序的整数列表中找到与给定值最接近的整数。
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 库中的某个地方而我错过了它？
采纳答案by dfa
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));
}
回答by AlbertoPL
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
请参阅：在数字集合中寻找最接近的匹配
回答by newacct
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.
我认为你所拥有的是最简单和最有效的方法。在排序列表中查找“最近”项并不是编程中常见的事情（您通常会寻找较大的项目或较小的项目）。这个问题只对数字类型有意义，所以不是很普遍，因此有一个库函数是不寻常的。
回答by Markus Lausberg
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;
}
}
回答by Galghamon
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 个可能的解决方案。当你对一个函数有两种可能的解决方案时，你的问题才真正开始：如果这不是最终答案，而只是确定最佳行动方案的一系列步骤中的第一个，而你没有得到的答案呢？ return 会提供更好的解决方案吗？唯一正确的做法是考虑两个答案并仅在最后比较进一步处理的结果。
Think of the square root function as a somewhat analogous problem to this.
将平方根函数视为与此类似的问题。
回答by Andreas Dolk
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 接口。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;
}
}
回答by SimonC
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);
}
}
回答by Brett Kail
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);
}
回答by user3367701
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];
}
回答by Nicolas Duponchel
Kotlin is so helpful
Kotlin 很有帮助
fun List<Int>.closestValue(value: Int) = minBy { abs(value - it) }
val values = listOf(1, 8, 4, -6)
println(values.closestValue(-7)) // -6
println(values.closestValue(2)) // 1
println(values.closestValue(7)) // 8
List doesn't need to be sorted BTW
列表不需要排序 BTW
