2009-07-27 13 views
20

Mi chiedo come si scriverà un semplice metodo java per trovare l'intero intero di un determinato valore in un elenco intero ordinato.Trova il valore più vicino in un elenco ordererd

Ecco il mio primo tentativo:

public class Closest { 

    private static List<Integer> integers = new ArrayList<Integer>(); 

    static { 
     for (int i = 0; i <= 10; i++) { 
      integers.add(Integer.valueOf(i * 10)); 
     } 
    } 

    public static void main(String[] args) { 

     Integer closest = null; 
     Integer arg = Integer.valueOf(args[0]); 

     int index = Collections.binarySearch(
       integers, arg); 

     if (index < 0) /*arg doesn't exist in integers*/ { 
      index = -index - 1; 
      if (index == integers.size()) { 
       closest = integers.get(index - 1); 
      } else if (index == 0) { 
       closest = integers.get(0); 
      } else { 
       int previousDate = integers.get(index - 1); 
       int nextDate = integers.get(index); 
       if (arg - previousDate < nextDate - arg) { 
        closest = previousDate; 
       } else { 
        closest = nextDate; 
       } 
      } 
     } else /*arg exists in integers*/ { 
      closest = integers.get(index); 
     } 
     System.out.println("The closest Integer to " + arg + " in " + integers 
       + " is " + closest); 
    } 
} 

Cosa ne pensate di questa soluzione? Sono sicuro che c'è un modo più pulito per fare questo lavoro ...

Forse un tale metodo esiste da qualche parte nelle librerie Java e l'ho perso ??

Manu

risposta

27

provare questo metodo poco:

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

alcuni casi di test:

private final static List<Integer> list = Arrays.asList(10, 20, 30, 40, 50); 

@Test 
public void closestOf21() { 
    assertThat(closest(21, list), is(20)); 
} 

@Test 
public void closestOf19() { 
    assertThat(closest(19, list), is(20)); 
} 

@Test 
public void closestOf20() { 
    assertThat(closest(20, list), is(20)); 
} 
+0

Penso che questo codice è elegante, ma non abbastanza veloce come il codice originale, perché si deve creare un nuova lista per ogni chiamata di metodo. – Galghamon

+0

riparato grazie :-) – dfa

+0

Un importante vantaggio di questo algoritmo è che non richiede 'Elenco ' da ordinare (come dovrebbe essere se si utilizza 'Collections.binarySearch (..)'). –

1

Penso che quello che hai è il modo più semplice e più efficace per farlo. Trovare l'elemento "più vicino" in una lista ordinata non è qualcosa che si incontra comunemente nella programmazione (di solito si cerca quello più grande o quello più piccolo). Il problema ha senso solo per i tipi numerici, quindi non è molto generalizzabile, e quindi sarebbe insolito avere una funzione di libreria per questo.

+0

In genere ma non solo i numeri: è applicabile a tutto ciò in cui si può misurare la 'distanza' In altre parole: ovunque si possa chiedere "quanto più grande/più piccolo". –

0

Non testato

int[] randomArray; // your array you want to find the closest 
     int theValue; // value the closest should be near to 

     for (int i = 0; i < randomArray.length; i++) { 
      int compareValue = randomArray[i]; 

      randomArray[i] -= theValue; 
     } 

     int indexOfClosest = 0; 
     for (int i = 1; i < randomArray.length; i++) { 
      int compareValue = randomArray[i]; 

      if(Math.abs(randomArray[indexOfClosest] > Math.abs(randomArray[i]){ 
       indexOfClosest = i; 
      } 
     } 
0

Penso che la tua risposta è probabilmente il modo più efficace per restituire un unico risultato.

Tuttavia, il problema con il vostro approccio è che ci sono 0 (se non ci sono liste), 1 o 2 possibili soluzioni. È quando hai due soluzioni possibili per una funzione che i tuoi problemi iniziano davvero: se questa non è la risposta finale, ma solo la prima di una serie di passaggi per determinare una linea d'azione ottimale e la risposta che non hai il ritorno avrebbe fornito una soluzione migliore? L'unica cosa corretta da fare sarebbe considerare entrambe le risposte e confrontare i risultati dell'ulteriore elaborazione solo alla fine.

Pensare alla funzione radice quadrata come un problema alquanto analogo a questo.

1

Per risolvere il problema, estenderei l'interfaccia comparabile con un metodo distanceTo. L'implementazione di distanceTo restituisce un doppio valore che rappresenta la distanza prevista e che è compatibile con il risultato dell'implementazione compareTo.

L'esempio seguente illustra l'idea con solo mele. È possibile scambiare il diametro in base a peso, volume o dolcezza.La borsa restituirà sempre la mela 'vicina' (più simile in termini di dimensioni, wight o sapore)

public interface ExtComparable<T> extends Comparable<T> { 
    public double distanceTo(T other); 
} 

public class Apple implements Comparable<Apple> { 
    private Double diameter; 

    public Apple(double diameter) { 
     this.diameter = diameter; 
    } 

    public double distanceTo(Apple o) { 
     return diameter - o.diameter; 
    } 

    public int compareTo(Apple o) { 
     return (int) Math.signum(distanceTo(o)); 
    } 
} 

public class AppleBag { 
    private List<Apple> bag = new ArrayList<Apple>(); 

    public addApples(Apple...apples){ 
     bag.addAll(Arrays.asList(apples)); 
     Collections.sort(bag); 
    } 

    public removeApples(Apple...apples){ 
     bag.removeAll(Arrays.asList(apples)); 
    } 

    public Apple getClosest(Apple apple) { 
     Apple closest = null; 
     boolean appleIsInBag = bag.contains(apple); 
     if (!appleIsInBag) { 
     bag.addApples(apple); 
     } 

     int appleIndex = bag.indexOf(apple); 
     if (appleIndex = 0) { 
     closest = bag.get(1); 
     } else if(appleIndex = bag.size()-1) { 
     closest = bag.get(bag.size()-2); 
     } else { 
     double absDistToPrev = Math.abs(apple.distanceTo(bag.get(appleIndex-1)); 
     double absDistToNext = Math.abs(apple.distanceTo(bag.get(appleIndex+1)); 
     closest = bag.get(absDistToNext < absDistToPrev ? next : previous); 
     } 

     if (!appleIsInBag) { 
     bag.removeApples(apple); 
     } 

     return closest; 
    } 
} 
0

Se non siete interessati in maniera massiccia sulle prestazioni (dato che l'insieme viene cercato per due volte), penso che con un set navigabile porta a codice più chiaro:

public class Closest 
{ 
    private static NavigableSet<Integer> integers = new TreeSet<Integer>(); 

    static 
    { 
    for (int i = 0; i <= 10; i++) 
    { 
     integers.add(Integer.valueOf(i * 10)); 
    } 
    } 

    public static void main(String[] args) 
    { 
    final Integer arg = Integer.valueOf(args[0]); 
    final Integer lower = integers.lower(arg); 
    final Integer higher = integers.higher(arg); 

    final Integer closest; 
    if (lower != null) 
    { 
     if (higher != null) 
     closest = (higher - arg > arg - lower) ? lower : higher; 
     else 
     closest = lower; 
    } 
    else 
     closest = higher; 

    System.out.println("The closest Integer to " + arg + " in " + integers + " is " + closest); 
    } 
} 
0

La soluzione sembra essere asintoticamente ottimale. Potrebbe essere leggermente più veloce (anche se probabilmente meno gestibile) se utilizzasse Math.min/max. Un buon JIT ha probabilmente delle caratteristiche intrinseche che lo rendono veloce.

int index = Collections.binarySearch(integers, arg); 
if (index < 0) { 
    int previousDate = integers.get(Math.max(0, -index - 2)); 
    int nextDate = integers.get(Math.min(integers.size() - 1, -index - 1)); 
    closest = arg - previousDate < nextDate - arg ? previousDate : nextDate; 
} else { 
    closest = integers.get(index); 
} 
1

una soluzione senza ricerca binaria (sfrutta la lista da ordinare):

public int closest(int value, int[] sorted) { 
    if(value < sorted[0]) 
    return sorted[0]; 

    int i = 1; 
    for(; i < sorted.length && value > sorted[i] ; i++); 

    if(i >= sorted.length) 
    return sorted[sorted.length - 1]; 

    return Math.abs(value - sorted[i]) < Math.abs(value - sorted[i-1]) ? 
     sorted[i] : sorted[i-1]; 
} 
Problemi correlati