Нахождение расстояния между двумя ближайшими элементами в массиве чисел

Question

Итак, я изучаю алгоритмы из этой книги, которую я купил, и у меня есть псевдокод для определения расстояния между двумя элементами closetst в массиве чисел

MinDistance(a[0...n-1])
Input: Array A of numbers
Output: Minimum Distance between two of its elements
dMin <- maximum integer

for i=0 to n-1 do
   for j=0 to n-1 do
      if i!=j and | A[i] - A[j] | < dMin
        dMin = | A[i]-A[j] |
return dMin

Однако я хотел улучшить это алгоритмическое решение. Измените то, что уже есть, или перепишите все вместе. Может кто-нибудь помочь? Я написал функцию и класс в Java для проверки псевдокода? Это верно? И еще раз, как я могу сделать это лучше с точки зрения эффективности.

//Scanner library allowing the user to input data
import java.lang.Math.*;

public class ArrayTester{
    //algorithm for finding the distance between the two closest elements in an array of numbers
    public int MinDistance(int [] ar){
    int [] a = ar;
    int aSize = a.length;
    int dMin = 0;//MaxInt
    for(int i=0; i< aSize; i++)
    {
        for(int j=i+1; j< aSize;j++)
        {   
            dMin = Math.min(dMin, Math.abs( a[i]-a[j] );
        }
    }
    return dMin;
}

    //MAIN
    public static void main(String[] args){

        ArrayTester at = new ArrayTester();
        int [] someArray = {9,1,2,3,16};
        System.out.println("NOT-OPTIMIZED METHOD");
        System.out.println("Array length = "+ someArray.length);
        System.out.println("The distance between the two closest elements: " + at.MinDistance(someArray));

    } //end MAIN

} //END CLASS

ТАК Я обновил функцию, чтобы минимизировать двойной вызов Math.abs. Что еще я могу сделать, чтобы улучшить это. Если бы я переписал его с помощью sort, он вообще поменял бы мои циклы for, или он был бы таким же, просто теоретически работал бы быстрее.

public int MinDistance(int [] ar){
        int [] a = ar;
        int aSize = a.length;
        int dMin = 0;//MaxInt
        for(int i=0; i< aSize; i++)
        {
            for(int j=i+1; j< aSize;j++)
            {   
                dMin = Math.min(dMin, Math.abs( a[i]-a[j] );
            }
        }
        return dMin;
    }

Answer 1

Одно очевидное улучшение эффективности: сначала отсортируйте целые числа, а затем посмотрите на соседние. Любое число будет ближайшим к соседу вверх или вниз.

Это меняет сложность от O (n ² ) до O (n log n). По общему признанию, для небольшого значения, показанного n, это не будет иметь существенного значения, но с точки зрения теоретической сложности это важно.

Одна микрооптимизация, которую вы, возможно, захотите выполнить: используйте локальную переменную для хранения результата Math.abs, тогда вам не нужно будет повторно вычислять ее, если она окажется меньше минимальной. В качестве альтернативы вы можете использовать dMin = Math.min(dMin, Math.abs(a[i] - a[j])).

Обратите внимание, что вы должны быть осторожны с граничными условиями - если вы разрешаете отрицательные числа, ваше вычитание может переполниться.

Answer 2

Прежде всего, прежде чем делать это быстро, сделайте это правильно.Почему dmin инициализируется с длиной массива?Если массив равен [1, 1000], результат вашего алгоритма будет 2 вместо 999.

Тогда почему вы заставляете j переходить от 0 к длине массива?Вы сравниваете каждую пару элементов дважды.Вы должны заставить j перейти от i + 1 к длине массива (что также позволит избежать сравнения i! = J).

Наконец, вы можете получить несколько наносекунд, избегая вызова Math.abs ()дважды.

И затем вы можете полностью изменить свой алгоритм, сначала отсортировав массив, как отмечено в других ответах.

Answer 3

Это наивное решение O (n ^ 2).

Лучший способ:

Сортировать массив, затем повторить его еще раз и проверить расстояние между отсортированными элементами.
Это будет работать, потому что они расположены в порядке возрастания, поэтому число с ближайшим значением смежно.

Это решение будет O (nlogn)

Answer 4

Теоретически вы можете получить решение O (n) путем

1. сортировки с shell radix sort (отредактировано, благодаря j_random_hacker за указание на это)
2. один проход, чтобы найти разницу между числами

Answer 5

Вот вопрос:

Сколько времени потребуется, чтобы найти минимальное расстояние, если массив был отсортирован?

Вы должны быть в состоянии закончить все остальное отсюда.

Answer 6

Сортировка массива сначала освободит нас от использования другого цикла FOR.

    public static int distclosest(int numbers[]) {
       Arrays.sort(numbers);
       int aSize = numbers.length;
       int dMin = numbers[aSize-1];

       for(int i=0; i<aSize-1; i++) {
                dMin = Math.min(dMin, numbers[i+1]-numbers[i]);
       }
       return dMin;
    }