Нахождение ближайшего числа в массиве

Question

Сначала в массиве мы должны найти, существует ли желаемое число в этом или нет? Если нет, то как мне найти номер ближе к указанному желаемому числу в Java?

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

Answer 2

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

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

Answer 3

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

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

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

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

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

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

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

Answer 4

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

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;

Answer 5

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

Answer 6

Несколько вещей, на которые стоит обратить внимание:

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

Arrays.asList(yourIntegerArray);

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

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

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

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

Answer 7

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

Answer 8

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

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

Answer 9

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

Если вы хотите найти более близкое число С ЛЮБОЙ РАССТОЯНИЕЮ по желаемому номеру (не имеет значения), вы можете запомнить последнее возможное значение. Если вы можете проверить

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 
}

Answer 10

Не хватает только семантики ближе.

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

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

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