java java方法来查找与给定编号最接近的匹配项。在未排序的整数数组中
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6599371/
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
java method to find nearest match to a given no. in unsorted array of integers
提问by sandy_bangalore
I wanted help regarding Java program to find out nearest match to any given integer in unsorted array of integers
我需要有关 Java 程序的帮助，以找出与未排序整数数组中的任何给定整数最接近的匹配项
Can I please have suggestions about:
我能否请您提出以下建议：
* How to get start off with this?
* Should i first sort the array
Thanks All
谢谢大家
回答by NPE
If you only need to perform the search once, you can scan the array from start to finish, keeping track of the value that's nearest to the one you're seeking.
如果您只需要执行一次搜索，您可以从头到尾扫描数组，跟踪最接近您要查找的值的值。
If you need to search in the same array repeatedly, you should pre-sort the array and then repeatedly use binary search.
如果需要在同一个数组中重复搜索，则应该对数组进行预排序，然后重复使用二分查找。
回答by Peter Lawrey
If you cannot sort the array, or you are only doing this once, you can do.
如果您无法对数组进行排序，或者您只执行一次，则可以这样做。
public static int closest1(int find, int... values) {
int closest = values[0];
for(int i: values)
if(Math.abs(closest - find) > Math.abs(i - find))
closest = i;
return closest;
}
This will return one closest value. If you are looking for a value equally between two values, you will get the first one.
这将返回一个最接近的值。如果您正在寻找两个值之间相等的值，您将获得第一个值。
An optimised version.
一个优化的版本。
public static int closest2(int find, int... values) {
int closest = values[0];
int distance = Math.abs(closest - find);
for(int i: values) {
int distanceI = Math.abs(i - find);
if(distance > distanceI) {
closest = i;
distance = distanceI;
}
}
return closest;
}
A multi-thread version
多线程版本
public static int closest3(final int find, final int... values) {
final int procs = Runtime.getRuntime().availableProcessors();
ExecutorService es = Executors.newFixedThreadPool(procs);
List<Future<Integer>> futures = new ArrayList<Future<Integer>>();
final int blockSize = values.length / procs;
for (int i = 0; i < procs; i++) {
final int start = blockSize * i;
final int end = Math.min(blockSize * (i + 1), values.length);
futures.add(es.submit(new Callable<Integer>() {
@Override
public Integer call() throws Exception {
int closest = values[start];
int distance = Math.abs(closest - find);
for (int i = start + 1; i < end; i++) {
int n = values[i];
int distanceI = Math.abs(n - find);
if (distance > distanceI) {
closest = i;
distance = distanceI;
}
}
return closest;
}
}));
}
es.shutdown();
int[] values2 = new int[futures.size()];
try {
for (int i = 0; i < futures.size(); i++)
values2[i] = futures.get(i).get();
return closest2(find, values2);
} catch (Exception e) {
throw new AssertionError(e);
}
}
running this test
运行这个测试
Random rand = new Random();
int[] ints = new int[100 * 1000 * 1000];
for (int i = 0; i < ints.length; i++)
ints[i] = rand.nextInt();
for (int i = 0; i < 5; i++) {
long start1 = System.nanoTime();
closest1(i, ints);
long time1 = System.nanoTime() - start1;
long start2 = System.nanoTime();
closest2(i, ints);
long time2 = System.nanoTime() - start2;
long start3 = System.nanoTime();
closest3(i, ints);
long time3 = System.nanoTime() - start3;
System.out.printf("closest1 took %,d ms, closest2 took %,d ms, closest3 took %,d ms %n", time1 / 1000 / 1000, time2 / 1000 / 1000, time3 / 1000 / 1000);
}
for 100 million values prints
打印 1 亿张值
closest1 took 623 ms, closest2 took 499 ms, closest3 took 181 ms
closest1 took 645 ms, closest2 took 497 ms, closest3 took 145 ms
closest1 took 625 ms, closest2 took 495 ms, closest3 took 134 ms
closest1 took 626 ms, closest2 took 494 ms, closest3 took 134 ms
closest1 took 627 ms, closest2 took 495 ms, closest3 took 134 ms
Using the second approach saves 0.8 ms per million entries. The third approach is much faster for large arrays, but is likley to be slower for smaller ones.
使用第二种方法每百万个条目节省 0.8 毫秒。第三种方法对于大型阵列要快得多，但对于较小的阵列可能会更慢。
回答by Costi Ciudatu
/**
* @return the index of the closest match to the given value
*/
int nearestMatch(int[] array, int value) {
if (array.length == 0) {
throw new IllegalArgumentException();
}
int nearestMatchIndex = 0;
for (int i = 1; i < array.length; i++) {
if ( Math.abs(value - array[nearestMatchIndex])
> Math.abs(value - array[i]) ) {
nearestMatchIndex = i;
}
}
return nearestMatchIndex;
}
回答by Sean Patrick Floyd
Yes, sort the arrayand then use Arrays.binarySearch(int[], int)
是的，对数组进行排序，然后使用Arrays.binarySearch(int[], int)
Returns:
index of the search key, if it is contained in the array; otherwise,(-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be>= 0if and only if the key is found.
返回：
搜索关键字的索引，如果它包含在数组中；否则，(-(insertion point) - 1)。插入点定义为将键插入数组的点：大于键的第一个元素的索引，如果数组中的所有元素都小于指定的键，则为 a.length。请注意，这保证了>= 0当且仅当找到键时返回值。
回答by Fred Foo
No, you don't need to pre-sort the array. Just run through it, recording the position and value of the current nearest match, updating it at each iteration if necessary. This takes O(n) time while sorting would take O(n lg n) (unless you do a counting sort, which is not always applicable).
不，您不需要对数组进行预排序。只需运行它，记录当前最近匹配的位置和值，如有必要，在每次迭代时更新它。这需要 O(n) 时间，而排序需要 O(n lg n) （除非您进行计数排序，这并不总是适用）。
Only if you want to do this operation repeatedly will sorting pay off.
只有当你想重复做这个操作时，排序才会有回报。
回答by Ray Toal
Don't sort the array first since it will modify the original array.
不要先对数组进行排序，因为它会修改原始数组。
Instead, loop through the array keeping track of the difference between the current array element and your given value (and the array element with the smallest difference so far). The complexity here is linear; you can't beat that with sorting.
相反，循环遍历数组，跟踪当前数组元素与给定值（以及迄今为止差异最小的数组元素）之间的差异。这里的复杂性是线性的；你无法通过排序打败它。
