java - 搜索数组以查找一定数量的最近值的方法

Question

该方法由于限制不能使用ArrayLists。该方法接受一个数组、要查找的所需值以及一定数量的邻近值。它仅使用整数和整数数组。这是我到目前为止所拥有的

/**
    * Return the k elements of a nearest to val.
    * The array a is not changed as a result of calling this method.
    * This method throws an IllegalArgumentException if k is negative.
    * This method returns an array of zero length if k == 0 or if
    * k > a.length.
    *
    * @param a the array to be searched
    * @param val the reference value
    * @param k the number of near elements to identify
    * @return the k elements a[i] such that ABS(a[i] - val)
    * are the k smallest evaluations
    *
    */
   public static int[] nearestK(int[] a, int val, int k) {

      int x = 0;
      int[] answer = new int[k];

      if (k < x || a.length == 0 || a == null)
      {
         throw new IllegalArgumentException();
      }

      if (k == 0 || k > a.length) 
      {
         int[] badAnswer = new int[0];
         return badAnswer;
      }

      int[] copy = Arrays.copyOf(a, a.length);

      Arrays.sort(copy);

      int nearest = copy[0];   
      for (int i = 0; (i < copy.length); i++) {

         if (Math.abs(nearest - val) > Math.abs(copy[i] - val)) {
            nearest = copy[i]; x = i; 
         }   

      }

      int index = 0;
      while (index < answer.length) {

         answer[index] = nearest;
         nearest = copy[x + (index + 1)];
         index++; 

      }
      return answer;




 }

这种方法有时有效，但我开始意识到它只在所需元素之后使用值。

即int[1,3,5,7,10,11,12} 这个方法，如果搜索 6，有 3 个最接近的值，只会返回7,10,11 作为数组。这显然是不正确的。我对 java 很陌生，所以此时我想知道有哪些替代方法或纠正此方法的方法。

Answer 1

这里有一个聪明的答案:不是按自然顺序对数组进行排序，而是根据到 val 的距离进行排序。然后，您需要做的就是选择前 k 个元素:

public static int[] nearestK(int[] a, int val, int k) {
    // omitted your checks for brevity
    final int value = val; // needs to be final for the comparator, you can also make the parameter final and skip this line
    Integer[] copy = new Integer[a.length]; // copy the array using autoboxing
    for (int i = 0; i < a.length; i++) {
        copy[i] = a[i];
    }
    Arrays.sort(copy, new Comparator<Integer>() { // sort it with a custom comparator
        @Override
        public int compare(Integer o1, Integer o2) {
            int distance1 = Math.abs(value - o1); 
            int distance2 = Math.abs(value - o2); 
            return Integer.compare(distance1, distance2);
        }
    });
    int[] answer = new int[k]; // pick the first k elements
    for (int i = 0; i < answer.length; i++) {
        answer[i] = copy[i];
    }
    return answer;
}