查找数组中最接近的数字
首先，我们必须在数组中查找是否存在所需的数字？ 如果没有，那么我如何在Java中找到给定所需数字的更接近的数字？
一个主意：
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; “更接近”的另一个常见定义是基于差异的平方。 大纲类似于romaintaz提供的大纲，除了你要计算
long d = ((long)desiredNumber - array[i]);
然后将(d * d)与最近的距离进行比较。
请注意 ，我输入的d为long而不是int以避免溢出，即使使用基于绝对值的计算也会发生溢出。 （例如，考虑当desiredValue至少是最大32位有符号值的一半时会发生什么，并且数组包含具有相应幅度但负号的值。）
最后，我编写了返回值的索引的方法，而不是值本身。 在这两种情况中的任何一种：
- 当数组的长度为零时，和
- 如果你添加一个“tolerance”参数来限制你将考虑作为匹配的最大差异，
你可以使用-1作为类似于indexOf规范的带外值。
//这会有效
public int nearest(int of, List 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; }
如果数组已排序，则执行修改后的二进制搜索。 基本上如果你没有找到数字，那么在搜索结束时返回下限。
伪代码返回最接近整数的列表。
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;
Array.indexOf()找出Array.indexOf()元素是否存在。 如果不是，则迭代一个数组并维护一个变量，该变量保存所需元素和第i个元素之间的差值的绝对值。 返回绝对差异最小的元素。
总体复杂度为O（2n） ，可以进一步减少到arrays上的单次迭代（即O（n） ）。 虽然不会有太大的不同。
唯一缺少的是更接近的语义。
如果你正在寻找六个，你的arrays有四个和八个，你会怎么做？
哪一个最接近？
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]; }
通过这种方式，您可以找到最接近所需数字的最后一个数字，因为bestDistanceFoundYet是常量，并且d记住最后一个值，使if （d <...） 。
如果你想通过所需的数字找到更近的数字WITH ANY DISTANCE（ d是无关紧要的），你可以记住最后一个可能的值。 如果你可以测试
if(d
有几点需要指出：
1 – 您可以使用将数组转换为列表
Arrays.asList(yourIntegerArray);
2 – 使用列表，您可以使用indexOf（）。
3 – 考虑一个场景，你有一个长度的列表，你想要最接近3的数字，你已经发现2在数组中，你知道3不是。 如果不检查其他数字，你可以得出结论，2是最好的，因为它不可能更接近。 我不确定indexOf（）是如何工作的，所以这可能实际上并没有加快你的速度。
4 – 扩展为3，假设indexOf（）不会花费更多时间来获取索引处的值。 然后，如果你想要一个数组中最接近3的数字并且你已经找到了1，并且还有更多的数字需要检查，那么检查数组中的2或4是否更快。
5 – 在3和4上扩展，我认为可以将它应用于浮点数和双精度数，尽管它需要使用小于1的步长…计算小的范围似乎超出了问题的范围，尽管。
// 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 l = new ArrayList (10) ; for(int i=0 ; i() { public int compare(Integer n1, Integer n2) { return n1*n1 - n2*n2 ; } } ) ; Integer first = l.get(0) ; System.out.println("nearest number is " + first) ; } }
int[] somenumbers = getAnArrayOfSomenumbers(); int numbertoLookFor = getTheNumberToLookFor(); boolean arrayContainsNumber = new HashSet(Arrays.asList(somenumbers)) .contains(numbertoLookfor);
它也很快。
哦 – 你想找到最近的号码？ 在这种情况下：
int[] somenumbers = getAnArrayOfSomenumbers(); int numbertoLookFor = getTheNumberToLookFor(); ArrayList l = new ArrayList ( 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));
哦 - 坚持：你是在追求最小二乘解决方案？
Collections.sort(l, new Comparator(){ 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));