Поиск ближайшего числа в массиве

Ответ 1

Идея:

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;

Ответ 2

Другое общее определение "ближе" основано на квадрате разницы. Схема похожа на схему, предоставленную romaintaz, за исключением того, что вы вычислили

long d = ((long)desiredNumber - array[i]);

а затем сравните (d * d) с ближайшим расстоянием.

Примечание, который я набрал d как long, а не int, чтобы избежать переполнения, что может произойти даже при вычислении на основе абсолютных значений. (Например, подумайте о том, что произойдет, когда desiredValue составляет как минимум половину максимального 32-разрядного знакового значения, а массив содержит значение с соответствующей величиной, но отрицательный знак.)

Наконец, я бы написал метод, чтобы вернуть индекс находящегося значения, а не самого значения. В любом из этих двух случаев:

• когда массив имеет длину 0 и
• если вы добавите параметр "допуска", который ограничивает максимальную разницу, которую вы считаете совпадением,

вы можете использовать -1 как внеполосное значение, подобное спецификации на indexOf.

Ответ 3

//Это будет работать

public int nearest(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;
}

Ответ 4

Если массив отсортирован, выполните модифицированный двоичный поиск. В принципе, если вы не найдете число, то в конце поиска верните нижнюю границу.

Ответ 5

Pseudocode для возврата списка ближайших целых чисел.

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;

Ответ 6

Array.indexOf(), чтобы узнать, существует ли элемент wheter. Если это не так, выполните итерацию по массиву и сохраните переменную, которая содержит абсолютное значение разности между желаемым и i -тым элементом. Возвращаемый элемент с наименьшей абсолютной разницей.

Общая сложность O (2n), которая может быть дополнительно сведена к одной итерации по массиву (это будет O (n)). Однако это не будет иметь особого значения.

Ответ 7

Единственное, чего не хватает, это семантика ближе.

Что вы делаете, если ищете шесть, и ваш массив имеет как четыре, так и восемь?

Какой из них ближе?

Ответ 8

   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<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 
}

Ответ 9

Несколько замечаний:

1 - Вы можете преобразовать массив в список, используя

Arrays.asList(yourIntegerArray);

2 - Используя список, вы можете просто использовать indexOf().

3. Рассмотрим сценарий, в котором у вас есть список некоторой длины, вы хотите, чтобы число, самое близкое к 3, вы уже обнаружили, что 2 находится в массиве, и вы знаете, что 3 нет. Не проверяя другие цифры, вы можете смело заключить, что 2 является лучшим, потому что невозможно быть ближе. Я не уверен, как работает indexOf(), поэтому это может не ускорить вас.

4 - Развернувшись на 3, скажем, что indexOf() занимает больше времени, чем получение значения по индексу. Тогда, если вы хотите, чтобы число, самое близкое к 3 в массиве, и вы уже нашли 1, и у вас есть еще много номеров для проверки, тогда будет быстрее просто проверить, есть ли 2 или 4 в массиве.

5 - Развернувшись на 3 и 4, я думаю, что можно было бы применить это к поплавкам и удвоениям, хотя для этого потребуется, чтобы вы использовали размер шага меньше 1... вычисляли, насколько малый кажется вне сферы действия вопрос, тем не менее.

Ответ 10

// paulmurray 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) ;  
    }
}

Ответ 11

int[] somenumbers = getAnArrayOfSomenumbers();
int numbertoLookFor = getTheNumberToLookFor();

boolean arrayContainsNumber = 
   new HashSet(Arrays.asList(somenumbers))
      .contains(numbertoLookfor);

Это тоже быстро.

Ох - вы хотели найти ближайший номер? В этом случае:

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));

Ох: зависание: вы были после решения наименьших квадратов?

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));