Функция Ha sh для отображения k ближайших данных в одну корзину

Question

У меня есть массив сказать [1, 2, 3, 4, 5, 10, 12, 6, 200, 300, 500]. Я пытаюсь разработать функцию ha sh так, чтобы все элементы, разделенные одинаковым расстоянием k, сталкивались в одной и той же позиции в выходном массиве, образуя связанный список в этом месте с заголовком связанного списка в этом месте. Это поможет найти ближайшие элементы по расстоянию, используя функцию ha sh. Я попробовал очень простую функцию ha sh h(j)=int(j/k), где k - расстояние, например, если k=5, то точки столкновения будут такими: [1, 2, 3, 4, 5] [6, 10] [12] [200] [300] [500]. Моя цель состоит в том, чтобы дать два числа функции ha sh, например, 1 и 2, и они должны вернуть мне ту же самую позицию 0 в массиве, сообщая мне, что они являются ближайшим соседом. Это должно выполняться в ожидаемом тета н пространстве и времени сложности.

Answer 1

Если вы не планируете иметь одинаковые числа в нескольких корзинах, это будет невозможно. Даже в вашем собственном примере 5 находится в другом сегменте, чем 6, но на самом деле ближе к 6, чем 10, который сгруппирован с 6.

Если вы разрешите одному и тому же числу появляться в нескольких сегментах, то вы можете получить группировка "ближайшего соседа" на основе порогового расстояния, но ваш результат будет выглядеть примерно так (при условии, что максимальное расстояние <5): </p>

[1,2,3,4,5] [2,3,4,5,6] [6,10] [10,12] [200] [300] [500]