Recherche du nombre le plus proche dans un tableau

Question

Dans un tableau, nous devons d'abord déterminer si un nombre désiré existe ou non dans ce tableau. Si non alors comment vais-je trouver plus près du nombre désiré en Java?

Answer 1

Array.indexOf() pour savoir si l'élément existe ou non. Si ce n'est pas le cas, parcourez un tableau et conservez une variable qui contient la valeur absolue de la différence entre l'élément désiré et i -th. Renvoie l'élément avec la plus petite différence absolue.

complexité globale est O (2n), qui peut encore être réduite à une seule itération sur un réseau (ce serait O (n)). Cela ne fera pas beaucoup de différence.

Answer 2

Une idée:

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 3

Si le tableau est trié, puis effectuez une recherche binaire modifiée. Fondamentalement, si vous ne trouvez pas le nombre, alors à la fin de la recherche, retournez la limite inférieure.

Answer 4

Il manque seulement la sémantique de plus proche.

Que faites-vous si vous cherchez six et votre tableau a quatre et huit?

Lequel est le plus proche?

Answer 5

Pseudocode pour renvoyer la liste des entiers les plus proches.

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 6

Une autre définition courante de "plus proche" est basée sur le carré de la différence. Le schéma est similaire à celle fournie par romaintaz, à l'exception que vous souhaitez calculer

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

puis comparer (d * d) à la distance la plus proche.

Remarqueque j'ai tapé d comme long plutôt que int pour éviter tout débordement, ce qui peut se produire même avec le calcul basé sur la valeur absolue. (Par exemple, pensez à ce qui se passe quand desiredValue est au moins la moitié de la valeur maximale de 32 bits signé, et le tableau contient une valeur de magnitude correspondante mais signe négatif.)

Enfin, j'écrire la méthode pour retourner l'index de la valeur localisée, plutôt que la valeur elle-même. Dans l'un de ces deux cas:

• lorsque le tableau a une longueur de zéro, et
• si vous ajoutez un paramètre « tolérance » qui limite la différence maximale vous considérer comme un match,

vous pouvez utiliser -1 comme une valeur hors bande similaire à la spécification sur indexOf.

Answer 7

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

De cette façon, vous trouvez le dernier numéro plus proche de nombre souhaité car bestDistanceFoundYet est constant et d mémoriser la dernière valeur passign si le (d < ...).

Si vous souhaitez trouver le plus proche numéro avec n'importe quelle distance par le nombre désiré (d n'est pas important), vous pouvez mémoriser la dernière valeur possible. Au cas vous pouvez tester

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 8

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

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

Il est rapide aussi.

Oh - vous vouliez trouver le numéro le plus proche? Dans ce cas:

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

Oh-accrocher: vous étiez après une solution des moindres carrés?

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

Answer 9

Quelques choses à signaler:

1 - Vous pouvez convertir le tableau à une liste à l'aide

Arrays.asList(yourIntegerArray); 

2 - À l'aide d'une liste, vous pouvez simplement utiliser indexOf().

3 - Considérons un scénario où vous avez une liste d'une certaine longueur, vous voulez que le nombre le plus proche de 3, vous avez déjà trouvé que 2 est dans le tableau, et vous savez que 3 ne l'est pas. Sans vérifier les autres chiffres, vous pouvez sans risque conclure que 2 est le meilleur, parce qu'il est impossible d'être plus proche. Je ne suis pas sûr de savoir comment indexOf() fonctionne, cependant, cela ne peut pas vous accélérer.

4 - En se développant sur 3, disons que indexOf() ne prend pas plus de temps que d'obtenir la valeur à un index. Ensuite, si vous voulez que le nombre le plus proche de 3 dans un tableau et vous avez déjà trouvé 1, et avez beaucoup plus de nombres à vérifier, alors il sera plus rapide de simplement vérifier si 2 ou 4 est dans le tableau.

5 - Expansion sur 3 et 4, je pense qu'il pourrait être possible d'appliquer à double et flotteurs, mais il faudrait que vous utilisez une taille de pas inférieure à 1 ... calculer le petit semble au-delà de la portée de la question, cependant.

Answer 10

// 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 11

// Cela fonctionne

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