Найдите самое близкое значение в заказанном списке

Я задаюсь вопросом, как Вы записали бы простой метод Java, находящий самое близкое Целое число к данному значению в отсортированном Целочисленном списке.

Вот моя первая попытка:

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

Что Вы думаете об этом решении? Я уверен, что существует более чистый способ сделать это задание.

Возможно, такой метод существует где-нибудь в библиотеках Java, и я пропустил его?

24
задан Vadim Kotov 17 July 2019 в 08:07
поделиться

8 ответов

попробуйте этот небольшой метод:

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

несколько тестов:

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));
}
33
ответ дан 28 November 2019 в 23:49
поделиться

Думаю, что вы have - это самый простой и эффективный способ сделать это. Нахождение «ближайшего» элемента в отсортированном списке - не то, что обычно встречается в программировании (обычно вы ищите тот, который больше, или тот, который меньше). Проблема имеет смысл только для числовых типов, поэтому она не очень универсальна, и поэтому было бы необычно иметь для нее библиотечную функцию.

1
ответ дан 28 November 2019 в 23:49
поделиться

To solve the problem, I'd extend the Comparable Interface by a distanceTo method. The implementation of distanceTo returns a double value that represents the intended distance and which is compatible with the result of the compareTo implementation.

The following example illustrates the idea with just apples. You can exchange diameter by weight, volume or sweetness. The bag will always return the 'closest' apple (most similiar in size, wight or taste)

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;
   }
}
1
ответ дан 28 November 2019 в 23:49
поделиться

Конечно, вы можете просто использовать цикл for для просмотра и отслеживания разницы между текущим значением и значением. Это выглядело бы чище, но было бы намного медленнее.

См .: Поиск ближайшего совпадения в наборе чисел

0
ответ дан 28 November 2019 в 23:49
поделиться

Не тестировалось

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
ответ дан 28 November 2019 в 23:49
поделиться

Я думаю, что ваш ответ, вероятно, является наиболее эффективным способом вернуть единственный результат.

Однако проблема с вашим подходом в том, что есть 0 (если нет списка), 1 , или 2 возможных решения. Когда у вас есть два возможных решения функции, которые действительно запускают ваши проблемы: что, если это не окончательный ответ, а только первый из серии шагов для определения оптимального курса действий, и ответ, который вы не сделали? возврат обеспечил бы лучшее решение? Единственно правильным решением было бы рассмотреть оба ответа и сравнить результаты дальнейшей обработки только в конце.

Думайте о функции квадратного корня как о проблеме, отчасти аналогичной этой.

0
ответ дан 28 November 2019 в 23:49
поделиться

Если вы не сильно заботитесь о производительности (учитывая, что набор просматривается дважды), я думаю, что использование набора с возможностью навигации приводит к более четкому коду:

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
ответ дан 28 November 2019 в 23:49
поделиться

Ваше решение кажется асимптотически оптимальным. Это могло бы быть немного быстрее (хотя, вероятно, менее обслуживаемым), если бы использовалось Math.min / max. Хороший JIT, вероятно, имеет встроенные функции, которые делают его быстрым.

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);
}
0
ответ дан 28 November 2019 в 23:49
поделиться