There was a task to find several numbers closest to the transferred value from the huge amount of data stored in the array. Found such an option. https://stackoverflow.com/questions/1187352/find-closest-value-in-an-ordererd-list It can be adapted by removing the closest value from the array for each pass, but this is too long. How to optimize what would the search go for the minimum number of passes?

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; }
  • It is possible to solve in one pass. And this code is just one pass and implements. What is the complexity of changing it to save multiple values? - Axifive
  • @IntFloat couldn’t figure out how to make it beautiful too - Ilya
  • And your list is sorted, or not? - VladD

1 answer 1

Do this:

  1. Get a list of the closest items sorted by distance, empty at the beginning. Let it be the resulting list.
  2. Go over this list
  3. Each element of this list is compared with the elements of the resulting list. Find the last index of the item that is closer to this one. If this is the last index of the list, and the list is full, do nothing, otherwise add the current item to the list, and if the list is full, delete the last item.
  4. At the end you will receive the desired list.

Code:

 public static List<Integer> closest_n(int of, List<Integer> in, int n) { List<Integer> closest = new ArrayList<Integer>(); List<Integer> diffs = new ArrayList<Integer>(); for (int v : in) { final int diff = Math.abs(v - of); int index = Collections.binarySearch(diffs, diff); if (index < 0) { index = -(index + 1); } if (index >= n) { continue; } closest.add(index, v); diffs.add(index, diff); if (closest.size() > n) { closest.remove(n); diffs.remove(n); } } return closest; }