Java 在数组中查找最接近的数字
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/519881/
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
Finding closest number in an array
提问by
In an array first we have to find whether a desired number exists in that or not? If not then how will I find nearer number to the given desired number in Java?
首先在数组中，我们必须找到其中是否存在所需的数字？如果不是，那么我将如何在 Java 中找到更接近给定所需数字的数字？
回答by Anton Gogolev
Array.indexOf()to find out wheter element exists or not. If it does not, iterate over an array and maintain a variable which holds absolute value of difference between the desired and i-th element. Return element with least absolute difference.
Array.indexOf()找出元素是否存在。如果不是，则迭代一个数组并维护一个变量，该变量保存所需i元素和第 -th 个元素之间的差异的绝对值。返回具有最小绝对差异的元素。
Overall complexity is O(2n), which can be further reduced to a single iteration over an array (that'd be O(n)). Won't make much difference though.
整体复杂度为O(2n)，可以进一步减少到对数组的单次迭代（即O(n)）。不过不会有太大区别。
回答by Romain Linsolas
An idea:
一个主意：
int nearest = -1;
int bestDistanceFoundYet = Integer.MAX_INTEGER;
// We iterate on the array...
for (int i = 0; i < array.length; i++) {
// if we found the desired number, we return it.
if (array[i] == desiredNumber) {
return array[i];
} else {
// else, we consider the difference between the desired number and the current number in the array.
int d = Math.abs(desiredNumber - array[i]);
if (d < bestDistanceFoundYet) {
// For the moment, this value is the nearest to the desired number...
bestDistanceFoundYet = d; // Assign new best distance...
nearest = array[i];
}
}
}
return nearest;
回答by Sesh
If the array is sorted, then do a modified binary search. Basically if you do not find the number, then at the end of search return the lower bound.
如果数组已排序，则进行修改后的二进制搜索。基本上如果你没有找到数字，那么在搜索结束时返回下限。
回答by Rob Wells
Only thing missing is the semantics of closer.
唯一缺少的是 close 的语义。
What do you do if you're looking for six and your array has both four and eight?
如果您正在寻找 6 个而您的阵列有 4 个和 8 个，您会怎么做？
Which one is closest?
哪一个最接近？
回答by lakshmanaraj
Pseudocode to return list of closest integers.
返回最接近整数列表的伪代码。
myList = new ArrayList();
if(array.length==0) return myList;
myList.add(array[0]);
int closestDifference = abs(array[0]-numberToFind);
for (int i = 1; i < array.length; i++) {
int currentDifference= abs(array[i]-numberToFind);
if (currentDifference < closestDifference) {
myList.clear();
myList.add(array[i]);
closestDifference = currentDifference;
} else {
if(currentDifference==closestDifference) {
if( myList.get(0) !=array[i]) && (myList.size() < 2) {
myList.add(array[i]);
}
}
}
}
return myList;
回答by joel.neely
Another common definition of "closer" is based on the square of the difference. The outline is similar to that provided by romaintaz, except that you'd compute
“更接近”的另一个常见定义是基于差异的平方。大纲类似于 romaintaz 提供的大纲，不同之处在于您要计算
long d = ((long)desiredNumber - array[i]);
and then compare (d * d)to the nearest distance.
然后(d * d)与最近的距离进行比较。
Notethat I've typed das longrather than intto avoid overflow, which can happen even with the absolute-value-based calculation.(For example, think about what happens when desiredValueis at least half of the maximum 32-bit signed value, and the array contains a value with corresponding magnitude but negative sign.)
请注意，我输入daslong而不是int为了避免溢出，即使使用基于绝对值的计算也会发生溢出。（例如，想想当desiredValue至少是最大 32 位有符号值的一半时会发生什么，并且数组包含一个具有相应大小但为负号的值。）
Finally, I'd write the method to return the index of the value located, rather than the value itself. In either of these two cases:
最后，我会编写方法来返回所定位值的索引，而不是值本身。在这两种情况中的任何一种中：
- when the array has a length of zero, and
- if you add a "tolerance" parameter that bounds the maximum difference you will consider as a match,
- 当数组的长度为零时，并且
- 如果您添加一个“公差”参数来限制您将视为匹配的最大差异，
you can use -1as an out-of-band value similar to the spec on indexOf.
您可以将其-1用作类似于规范的带外值indexOf。
回答by alepuzio
int d = Math.abs(desiredNumber - array[i]);
if (d < bestDistanceFoundYet) {
// For the moment, this value is the nearest to the desired number...
nearest = array[i];
}
In this way you find the last number closer to desired number because bestDistanceFoundYetis constant and dmemorize the last value passign the if (d<...).
通过这种方式，您会发现最后一个数字更接近所需数字，因为bestDistanceFoundYet是常数，并且d 会记住最后一个值 passign if (d<...)。
If you want found the closer number WITH ANY DISTANCE by the desired number (dis'nt matter), you can memorize the last possibile value. At the if you can test
如果您想通过所需的数字（d无关紧要）找到与任何距离更接近的数字，您可以记住最后一个可能的值。如果你可以测试
if(d<last_d_memorized){ //the actual distance is shorter than the previous
// For the moment, this value is the nearest to the desired number...
nearest = array[i];
d_last_memorized=d;//is the actual shortest found delta
}
回答by paulmurray
int[] somenumbers = getAnArrayOfSomenumbers();
int numbertoLookFor = getTheNumberToLookFor();
boolean arrayContainsNumber =
new HashSet(Arrays.asList(somenumbers))
.contains(numbertoLookfor);
It's fast, too.
它也很快。
Oh - you wanted to find the nearest number? In that case:
哦 - 你想找到最近的数字吗？在这种情况下：
int[] somenumbers = getAnArrayOfSomenumbers();
int numbertoLookFor = getTheNumberToLookFor();
ArrayList<Integer> l = new ArrayList<Integer>(
Arrays.asList(somenumbers)
);
Collections.sort(l);
while(l.size()>1) {
if(numbertoolookfor <= l.get((l.size()/2)-1)) {
l = l.subList(0, l.size()/2);
}
else {
l = l.subList(l.size()/2, l.size);
}
}
System.out.println("nearest number is" + l.get(0));
Oh - hang on: you were after a least squares solution?
哦 - 等等：你是在追求最小二乘解决方案吗？
Collections.sort(l, new Comparator<Integer>(){
public int compare(Integer o1, Integer o2) {
return (o1-numbertoLookFor)*(o1-numbertoLookFor) -
(o2-numbertoLookFor)*(o2-numbertoLookFor);
}});
System.out.println("nearest number is" + l.get(0));
回答by ArtOfWarfare
A few things to point out:
有几点需要指出：
1 - You can convert the array to a list using
1 - 您可以使用将数组转换为列表
Arrays.asList(yourIntegerArray);
2 - Using a list, you can just use indexOf().
2 - 使用列表，您可以只使用 indexOf()。
3 - Consider a scenario where you have a list of some length, you want the number closest to 3, you've already found that 2 is in the array, and you know that 3 is not. Without checking the other numbers, you can safely conclude that 2 is the best, because it's impossible to be closer. I'm not sure how indexOf() works, however, so this may not actually speed you up.
3 - 考虑这样一个场景，您有一个具有一定长度的列表，您想要最接近 3 的数字，您已经发现 2 在数组中，而您知道 3 不在。在不检查其他数字的情况下，您可以安全地得出结论，2 是最好的，因为不可能更接近。但是，我不确定 indexOf() 是如何工作的，因此这实际上可能不会加快您的速度。
4 - Expanding on 3, let's say that indexOf() takes no more time than getting the value at an index. Then if you want the number closest to 3 in an array and you already have found 1, and have many more numbers to check, then it'll be faster to just check whether 2 or 4 is in the array.
4 - 在 3 上展开，假设 indexOf() 花费的时间不超过在索引处获取值的时间。然后，如果您想要数组中最接近 3 的数字并且您已经找到了 1，并且还有更多数字要检查，那么只检查 2 或 4 是否在数组中会更快。
5 - Expanding on 3 and 4, I think it might be possible to apply this to floats and doubles, although it would require that you use a step size smaller than 1... calculating how small seems beyond the scope of the question, though.
5 - 在 3 和 4 上进行扩展，我认为可以将其应用于浮点数和双精度数，尽管它要求您使用小于 1 的步长...计算似乎超出问题范围的小数，尽管.
回答by Juanma
// paulmurray's answer to your question is really the best :
// The least square solution is way more elegant,
// here is a test code where numbertoLookFor
// is zero, if you want to try ...
import java.util.* ;
public class main {
public static void main(String[] args)
{
int[] somenumbers = {-2,3,6,1,5,5,-1} ;
ArrayList<Integer> l = new ArrayList<Integer>(10) ;
for(int i=0 ; i<somenumbers.length ; i++)
{
l.add(somenumbers[i]) ;
}
Collections.sort(l,
new java.util.Comparator<Integer>()
{
public int compare(Integer n1, Integer n2)
{
return n1*n1 - n2*n2 ;
}
}
) ;
Integer first = l.get(0) ;
System.out.println("nearest number is " + first) ;
}
}
