Зачем сортировать перед решением

Для [8,1,5] полный перебор сравнил бы три пары. После сортировки [1,5,8] достаточно разностей 4 и 3: минимальная пара — соседние 5 и 8.

Как найти минимальную разность пары?

Найти минимальную абсолютную разницу между двумя разными элементами.

Сравнение всех пар индексов

Вычислить разницу для всех пар индексов и взять минимум.

Почему число пар растёт квадратично?

Пар O(n²), хотя после упорядочивания большинство пар заведомо разделены промежуточным значением.

Почему оптимальная пара соседствует после сортировки?

В отсортированном массиве пара с минимальной разницей обязательно соседняя: любой элемент между ними образует не большую разницу с одним концом.

Что означает best после проверки очередного соседа?

После проверки соседей до i best равен минимальной разнице среди обработанного префикса.

Сортируем копию и сравниваем соседние значения

Потребовать хотя бы два элемента, отсортировать копию и проверить разницы a[i]-a[i-1].

Минимальная разность на C++17 и Python 3

C++17

#include <algorithm>
#include <cassert>
#include <stdexcept>
#include <vector>
using namespace std;

long long minimumDifference(vector<int> values) {
    if (values.size() < 2) throw invalid_argument("need two values");
    sort(values.begin(), values.end());
    long long best = static_cast<long long>(values[1]) - values[0];
    for (int i = 2; i < static_cast<int>(values.size()); ++i) {
        best = min(best, static_cast<long long>(values[i]) - values[i - 1]);
    }
    return best;
}

int main() {
    assert(minimumDifference({8, 1, 5}) == 3);
    assert(minimumDifference({2, 2}) == 0);
}

Python 3

def minimum_difference(values: list[int]) -> int:
    if len(values) < 2:
        raise ValueError("need two values")
    ordered = sorted(values)
    best = ordered[1] - ordered[0]
    for index in range(2, len(ordered)):
        best = min(best, ordered[index] - ordered[index - 1])
    return best


assert minimum_difference([8, 1, 5]) == 3
assert minimum_difference([2, 2]) == 0

Цена упорядочивания и одного линейного прохода

O(n log n) времени и O(n) памяти из-за копии. При разрешённом изменении входа дополнительная память зависит от реализации сортировки.

Дубликаты, короткий ввод и переполнение разности

Меньше двух элементов; дубликаты дают ответ 0; отрицательные значения; разность может переполнить int.

Какие наборы подтверждают доказательство о соседях?

[8,1,5] -> 3, [2,2] -> 0, [-10,-3,4] -> 7, один элемент — ошибка.

Когда сортировка превращает глобальный поиск в локальный?

Нужно сравнивать пары по расстоянию, пересечению или соседству, а исходный порядок не важен.

Когда исходный порядок запрещено терять?

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

Мини-проверка: может ли лучшая пара быть несоседней?

Вопрос: почему несоседняя пара не может быть единственной оптимальной? Ответ: промежуточный элемент делит её разницу на две неотрицательные части.

Мини-проверка: что теряется при сортировке значений?

Вопрос: что потеряется при сортировке значений? Ответ: исходные позиции; при необходимости сортируют пары (value,index).

Проследите соседние разности после сортировки

Для [12,3,17,8] сначала выпишите все шесть пар, затем отсортированные соседние разницы и сравните работу.

Найдите ближайшую пару самостоятельно

Задача 1

Верните пару исходных индексов с минимальной абсолютной разницей; при равенстве выберите лексикографически меньшую пару индексов.

Сортировка сводит все пары к соседним кандидатам

Сортировка полезна не сама по себе: она делает потенциально связанные элементы соседями.