Поиск двух ближайших номеров в списке с использованием сортировки

Question

Если мне задан список целых чисел/поплавков, как бы найти два ближайших номера, используя сортировку?

Answer 1

Такой метод будет делать то, что вы хотите:

>>> def minDistance(lst): 
    lst = sorted(lst) 
    index = -1 
    distance = max(lst) - min(lst) 
    for i in range(len(lst)-1): 
     if lst[i+1] - lst[i] < distance: 
      distance = lst[i+1] - lst[i] 
      index = i 
    for i in range(len(lst)-1): 
     if lst[i+1] - lst[i] == distance: 
      print lst[i],lst[i+1] 

В первом for цикле мы узнаем, минимальное расстояние, а во втором цикле, мы выводим все пары с этим расстоянием. Работает следующим образом:

>>> lst = (1,2,3,6,12,9,1.4,145,12,83,53,12,3.4,2,7.5) 
>>> minDistance(lst) 
2 2 
12 12 
12 12 
>>> 

Answer 2

Это может быть несколько возможностей. Рассмотрите этот список

[0,1, 20, 25, 30, 200, 201] 

[0,1] и [200, 201] являются самыми близкими.

Answer 3

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

Я не думаю, что вам нужен алгоритм сортировки, в скажем, но может быть просто своего рода «чемпион» алгоритм, как этот:

def smallestDistance(self, arr): 
    championI = -1 
    championJ = -1 
    champDistance = sys.maxint 
    i = 0 
    while i < arr.length: 
     j = i + 1 
     while j < arr.length: 
      if math.fabs(arr[i] - arr[j]) < champDistance: 
       championI = i 
       championJ = j 
       champDistance = math.fabs(arr[i] - arr[j]) 
      j += 1 
     i += 1 
    r = [arr[championI], arr[championJ]] 
    return r 

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

Я думаю, что популярный алгоритм сортировки, известный как сортировка пузырьков, сделает это довольно хорошо. Хотя работает при возможном O(n^2) времени, если это имеет значение для вас ...

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

def bubblesort(A): 
    for i in range(len(A)): 
    for k in range(len(A) - 1, i, -1): 
     if (A[k] < A[k - 1]): 
     swap(A, k, k - 1) 

def swap(A, x, y): 
    tmp = A[x] 
    A[x] = A[y] 
    A[y] = tmp 

Вы можете просто немного изменить алгоритм, чтобы соответствовать вашим целям, если вы настаиваете на этом, используя алгоритм сортировки. Тем не менее, я думаю, что начальная функция также работает ...

надеюсь, что это поможет.