Если мне задан список целых чисел/поплавков, как бы найти два ближайших номера, используя сортировку?Поиск двух ближайших номеров в списке с использованием сортировки
ответ
Такой метод будет делать то, что вы хотите:
>>> 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
>>>
Это может быть несколько возможностей. Рассмотрите этот список
[0,1, 20, 25, 30, 200, 201]
[0,1] и [200, 201] являются самыми близкими.
Хосе имеет действительный бал. Тем не менее, вы можете просто рассматривать эти случаи равными и не заботиться о возвращении того или другого.
Я не думаю, что вам нужен алгоритм сортировки, в скажем, но может быть просто своего рода «чемпион» алгоритм, как этот:
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
Вы можете просто немного изменить алгоритм, чтобы соответствовать вашим целям, если вы настаиваете на этом, используя алгоритм сортировки. Тем не менее, я думаю, что начальная функция также работает ...
надеюсь, что это поможет.
- 1. Сортировки ближайших номеров с помощью массива
- 2. Поиск номеров в списке с использованием бинарного поиска Помощь
- 3. Нахождение N ближайших номеров
- 4. Поиск ближайших мест с использованием GoogleAPI
- 5. Поиск ближайших возможных значений из двух словарей
- 6. Поиск номеров в списке и замена другим
- 7. Округление номеров до ближайших сотых в Silverlight
- 8. Поиск одинаковых и последовательных номеров в списке
- 9. Поиск среднего числа n номеров в списке
- 10. Сортировка строки с использованием номеров сортировки для сортировки также
- 11. Поиск «ближайших» строк в списке Python (в алфавитном порядке)
- 12. Печать номеров последовательно с использованием двух потоков
- 13. Поиск номеров в строке?
- 14. Поиск ближайших данных?
- 15. Поиск ближайших пользователей приложения
- 16. Solr Поиск ближайших совпадений
- 17. Поиск ближайших соседей K
- 18. Поиск ближайших значений в массиве
- 19. Сопротивление звукозаписи - поиск ближайших совпадений
- 20. Поиск ближайших координат в массиве?
- 21. Поиск ближайших дат в SQL
- 22. поиск ближайших строк с применением в R
- 23. Поиск двух ближайших чисел для любого поплавка из списка
- 24. Поиск ближайших соседей узлам с использованием взвешенных отношений
- 25. Поиск данных в списке с использованием linq
- 26. Поиск ближайших местоположений с использованием API Карт Google
- 27. поиск ближайших местоположений (долгота и широта) с использованием jquery
- 28. Поиск недостающих номеров в списке имен файлов в одном запросе
- 29. Рейтинг номеров с # N/A в списке
- 30. Поиск индексов чисел, ближайших к нулю (список)
Почему вы устанавливаете индекс на -1? – PythonSOS
@PythonSOS Я просто хотел определить переменную 'index' для следующего использования. Это начальное значение не будет использоваться нигде. Вы можете заменить '-1' на любое число. – EbraHim
также, будет ли это работать, если в списке есть два числа, которые являются точными? например, если у меня есть [3,3,4], он должен вернуться [3,3], а не [3,4] – PythonSOS