Алгоритм JavaScript: минимальные расстояния

Для сегодняшнего алгоритма мы собираемся написать функцию с именем minimumDistances, которая будет принимать массив a в качестве входных данных.

В этой функции нам дан массив целых чисел. Каждое значение находится по его индексу. Цель этой функции - найти любую пару совпадающих значений в массиве и определить расстояние между этими двумя совпадающими значениями, вычислив разность их индексов. После вычисления различий определите, какая совпадающая пара имеет наименьшее расстояние, и выведите это значение. Если подходящих пар не существует, функция вернет -1. Вот пример:

let a = [2,5,3,7,2,3];

В нашем примере массива выше единственными числами, имеющими совпадающие значения, являются 2 и 3.

Индексы двойки - это a [0] и a [4]. Если вычесть индексы 4 — 0 = 4, мы получим 4.

Индексы тройки - это a [2] и a [5]. Если вычесть индексы 5 — 2 = 3, мы получим 3.

Из двух расстояний (4 и 3) функция вернет минимальное значение расстояния 3.

Давайте превратим это в код.

let distances = [];

Переменная distances будет массивом, который будет содержать расстояния всех совпадающих пар из нашего входного массива.

for(let i = 0; i<a.length; i++){
    if(a.indexOf(a[i]) !== a.lastIndexOf(a[i])){
      let minDistance = a.lastIndexOf(a[i]) - a.indexOf(a[i]);
      distances.push(minDistance);
    }
}

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

let minDistance = a.lastIndexOf(a[i]) - a.indexOf(a[i]);
distances.push(minDistance);

Когда это происходит, мы берем индексы совпадающих чисел и вычитаем их. Мы помещаем различия или расстояние в наш массив distances.

if(distances.length === 0){
    return -1;
}else{
    distances.sort(function(a, b) {
      return a - b;
    });
    
    return distances[0];
}

Если в массиве нет подходящих пар, мы узнаем об этом, потому что наш массив distances останется пустым. Если это правда, мы вернем -1.

Если нет, то вернем наименьшее расстояние. Мы делаем это путем сортировки массива. Мы используем метод sort() вместе с функцией сравнения внутри метода sort() для сортировки нашего массива. Функция сравнения помогает определить порядок сортировки, сравнивая наши значения в виде чисел, а не строк (метод по умолчанию). Это сделано для предотвращения странного порядка сортировки, когда у нас есть массив, содержащий комбинацию однозначных и многозначных чисел.

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

Вот остальной код:

function minimumDistances(a) {
    let distances = [];
    for(let i = 0; i<a.length; i++){
        if(a.indexOf(a[i]) !== a.lastIndexOf(a[i])){
        let minDistance = a.lastIndexOf(a[i]) - a.indexOf(a[i]);
            distances.push(minDistance);
        }
    }
  
    if(distances.length === 0){
        return -1;
    }else{
        distances.sort(function(a, b) {
          return a - b;
        });
    
        return distances[0];
    }
}

Если вы нашли этот алгоритм полезным или полезным, ознакомьтесь с другими моими статьями о решениях для алгоритмов JavaScript: