I’ll rename the function take_closest to conform with PEP8 naming conventions.
If you mean quick-to-execute as opposed to quick-to-write, min should not be your weapon of choice, except in one very narrow use case. The min solution needs to examine every number in the list and do a calculation for each number. Using bisect.bisect_left instead is almost always faster.
The “almost” comes from the fact that bisect_left requires the list to be sorted to work. Hopefully, your use case is such that you can sort the list once and then leave it alone. Even if not, as long as you don’t need to sort before every time you call take_closest, the bisect module will likely come out on top. If you’re in doubt, try both and look at the real-world difference.
from bisect import bisect_left
def take_closest(myList, myNumber):
"""
Assumes myList is sorted. Returns closest value to myNumber.
If two numbers are equally close, return the smallest number.
"""
pos = bisect_left(myList, myNumber)
if pos == 0:
return myList[0]
if pos == len(myList):
return myList[-1]
before = myList[pos - 1]
after = myList[pos]
if after - myNumber < myNumber - before:
return after
else:
return before
Bisect works by repeatedly halving a list and finding out which half myNumber has to be in by looking at the middle value. This means it has a running time of O(log n) as opposed to the O(n) running time of the highest voted answer. If we compare the two methods and supply both with a sorted myList, these are the results:
$ python -m timeit -s " from closest import take_closest from random import randint a = range(-1000, 1000, 10)" "take_closest(a, randint(-1100, 1100))" 100000 loops, best of 3: 2.22 usec per loop $ python -m timeit -s " from closest import with_min from random import randint a = range(-1000, 1000, 10)" "with_min(a, randint(-1100, 1100))" 10000 loops, best of 3: 43.9 usec per loop
So in this particular test, bisect is almost 20 times faster. For longer lists, the difference will be greater.
What if we level the playing field by removing the precondition that myList must be sorted? Let’s say we sort a copy of the list every time take_closest is called, while leaving the min solution unaltered. Using the 200-item list in the above test, the bisect solution is still the fastest, though only by about 30%.
This is a strange result, considering that the sorting step is O(n log(n))! The only reason min is still losing is that the sorting is done in highly optimalized c code, while min has to plod along calling a lambda function for every item. As myList grows in size, the min solution will eventually be faster. Note that we had to stack everything in its favour for the min solution to win.
Для неотсортированного массива. Для отсортированного лучше использовать бинпоиск.
Python 3.4+: tio.run
def f(a, val):
return min((x for x in a if x > val), default=None)
a = [1, 2, 5, 22, 33, 44, 312]
print(f(a, 3))
print(f(a, 10))
print(f(a, 1000))
Более ранние версии: tio.run
def f(a, val):
return min([x for x in a if x > val] or [None])
a = [1, 2, 5, 22, 33, 44, 312]
print(f(a, 3))
print(f(a, 10))
print(f(a, 1000))
Вывод в обоих случаях:
5
22
None
-
-
Actions
Automate any workflow
-
Packages
Host and manage packages
-
Security
Find and fix vulnerabilities
-
Codespaces
Instant dev environments
-
Copilot
Write better code with AI
-
Code review
Manage code changes
-
Issues
Plan and track work
-
Discussions
Collaborate outside of code
Explore
-
All features
-
Documentation
-
GitHub Skills
-
Blog
-
-
For
-
Enterprise
-
Teams
-
Startups
-
Education
By Solution
-
CI/CD & Automation
-
DevOps
-
DevSecOps
Case Studies
-
Customer Stories
-
Resources
-
-
-
GitHub Sponsors
Fund open source developers
-
The ReadME Project
GitHub community articles
Repositories
-
Topics
-
Trending
-
Collections
-
- Pricing
Дан отсортированный массив целых чисел, найти k ближайшие элементы к target в массиве, где k а также target заданы положительные целые числа.
The target может присутствовать или отсутствовать во входном массиве. Если target меньше или равно первому элементу входного массива, вернуть первым k элементы. Точно так же, если target больше или равно последнему элементу входного массива, вернуть последний k элементы. Возвращаемые элементы должны быть в том же порядке, что и во входном массиве.
Например,
Input: [10, 12, 15, 17, 18, 20, 25], k = 4, target = 16
Output: [12, 15, 17, 18]
Input: [2, 3, 4, 5, 6, 7], k = 3, target = 1
Output: [2, 3, 4]
Input: [2, 3, 4, 5, 6, 7], k = 2, target = 8
Output: [6, 7]
Потренируйтесь в этой проблеме
Идея состоит в том, чтобы выполнить линейный поиск, чтобы найти точку вставки. i. Точка вставки определяется как точка, в которой ключ target будет вставлен в массив, т. е. индекс первого элемента больше ключа, или размер массива, если все элементы в массиве меньше указанного ключа. Затем сравните элементы вокруг точки вставки. i чтобы получить первый k ближайшие элементы. Временная сложность этого решения O(n), куда n это размер ввода.
Мы также можем найти точку вставки i с использованием алгоритм бинарного поиска, который работает в O(log(n)) время. С момента обнаружения k ближайший элемент занимает O(k) время, общая временная сложность этого решения равна O(log(n) + k). Ниже приведена реализация на C, C++, Java и Python, основанная на этой идее:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <stdio.h> #include <stdlib.h> // Функция для поиска в указанном массиве `nums` ключа `target` // используя алгоритм бинарного поиска int binarySearch(int nums[], int n, int target) { int low = 0; int high = n – 1; while (low <= high) { int mid = low + (high – low) / 2; if (nums[mid] < target) { low = mid + 1; } else if (nums[mid] > target) { high = mid – 1; } else { return mid; // ключ найден } } return low; // ключ не найден } // Функция для поиска `k` элементов, ближайших к `target`, в отсортированном целочисленном массиве `nums` void findKClosestElements(int nums[], int target, int k, int n) { // найти точку вставки с помощью алгоритма бинарного поиска int i = binarySearch(nums, n, target); int left = i – 1; int right = i; // запустить `k` раз while (k— > 0) { // сравниваем элементы по обе стороны от точки вставки `i` // чтобы получить первые `k` ближайших элементов if (left < 0 || (right < n && abs(nums[left] – target) > abs(nums[right] – target))) { right++; } else { left—; } } // вывести `k` ближайших элементов left++; while (left < right) { printf(“%d “, nums[left]); left++; } } int main(void) { int nums[] = { 10, 12, 15, 17, 18, 20, 25 }; int n = sizeof(nums) / sizeof(nums[0]); int target = 16, k = 4; findKClosestElements(nums, target, k, n); return 0; } |
Скачать Выполнить код
результат:
12 15 17 18
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Функция для поиска `k` ближайших элементов к `target` в отсортированном целочисленном векторе `input` vector<int> findKClosestElements(vector<int> const &input, int target, int k) { // найти точку вставки с помощью алгоритма бинарного поиска int i = lower_bound(input.begin(), input.end(), target) – input.begin(); int left = i – 1; int right = i; // запустить `k` раз while (k— > 0) { // сравниваем элементы по обе стороны от точки вставки `i` // чтобы получить первые `k` ближайших элементов if (left < 0 || (right < input.size() && abs(input[left] – target) > abs(input[right] – target))) { right++; } else { left—; } } // вернуть `k` ближайших элементов return vector<int>(input.begin() + left + 1, input.begin() + right); } int main() { vector<int> input = { 10, 12, 15, 17, 18, 20, 25 }; int target = 16, k = 4; vector<int> result = findKClosestElements(input, target, k); for (int i: result) { cout << i << ” “; } return 0; } |
Скачать Выполнить код
результат:
12 15 17 18
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
import java.util.Arrays; import java.util.Collections; import java.util.List; class Main { // Функция для поиска `k` элементов, ближайших к `target`, в отсортированном списке `input` public static List<Integer> findKClosestElements(List<Integer> input, int k, int target) { // найти точку вставки с помощью алгоритма бинарного поиска int i = Collections.binarySearch(input, target); // Collections.binarySearch() возвращает `-(точка вставки) – 1` // если ключ не содержится в списке if (i < 0) { i = –(i + 1); } int left = i – 1; int right = i; // запустить `k` раз while (k— > 0) { // сравниваем элементы по обе стороны от точки вставки `i` // чтобы получить первые `k` ближайших элементов if (left < 0 || (right < input.size() && Math.abs(input.get(left) – target) > Math.abs(input.get(right) – target))) { right++; } else { left—; } } // вернуть `k` ближайших элементов return input.subList(left + 1, right); } public static void main(String[] args) { List<Integer> input = Arrays.asList(10, 12, 15, 17, 18, 20, 25); int target = 16, k = 4; System.out.println(findKClosestElements(input, k, target)); } } |
Скачать Выполнить код
результат:
[12, 15, 17, 18]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
# Функция для поиска в указанном массиве `nums` ключа `target` # с использованием алгоритма бинарного поиска def binarySearch(nums, target): low = 0 high = len(nums) – 1 while low <= high: mid = low + (high – low) // 2 if nums[mid] < target: low = mid + 1 elif nums[mid] > target: high = mid – 1 else: return mid # Ключ # найден return low # Ключ # не найден # Функция для поиска `k` элементов, ближайших к `target`, в отсортированном массиве целых чисел `nums` def findKClosestElements(nums, target, k): # найти точку вставки с помощью алгоритма бинарного поиска i = binarySearch(nums, target) left = i – 1 right = i # запускается `k` раз while k > 0: # сравнить элементы по обе стороны от точки вставки `i` #, чтобы получить первые `k` ближайших элементов if left < 0 or (right < len(nums) and abs(nums[left] – target) > abs(nums[right] – target)): right = right + 1 else: left = left – 1 k = k – 1 # возвращает `k` ближайших элементов return nums[left+1: right] if __name__ == ‘__main__’: nums = [10, 12, 15, 17, 18, 20, 25] target = 16 k = 4 print(findKClosestElements(nums, target, k)) |
Скачать Выполнить код
результат:
[12, 15, 17, 18]
Приведенное выше решение для выполнения двоичного поиска, чтобы найти точку вставки, а затем пытается найти k ближайшие элементы. Однако мы можем объединить всю логику в одну процедуру бинарного поиска. Вот как алгоритм будет выглядеть в C, Java и Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <stdio.h> #include <stdlib.h> // Функция для поиска `k` элементов, ближайших к `target`, в отсортированном целочисленном массиве `nums` void findKClosestElements(int nums[], int target, int k, int n) { int left = 0; int right = n; while (right – left >= k) { if (abs(nums[left] – target) > abs(nums[right] – target)) { left++; } else { right—; } } // вывести `k` ближайших элементов while (left <= right) { printf(“%d “, nums[left]); left++; } } int main(void) { int nums[] = { 10, 12, 15, 17, 18, 20, 25 }; int n = sizeof(nums) / sizeof(nums[0]); int target = 16, k = 4; findKClosestElements(nums, target, k, n); return 0; } |
Скачать Выполнить код
результат:
12 15 17 18
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
import java.util.Arrays; import java.util.List; import java.util.stream.Collectors; class Main { // Функция для поиска `k` элементов, ближайших к `target`, в отсортированном целочисленном массиве `nums` public static List<Integer> findKClosestElements(int[] nums, int k, int target) { int left = 0; int right = nums.length – 1; while (right – left >= k) { if (Math.abs(nums[left] – target) > Math.abs(nums[right] – target)) { left++; } else { right—; } } return Arrays.stream(nums, left, right + 1).boxed() .collect(Collectors.toList()); } public static void main(String[] args) { int[] nums = {10, 12, 15, 17, 18, 20, 25 }; int target = 16, k = 4; System.out.println(findKClosestElements(nums, k, target)); } } |
Скачать Выполнить код
результат:
[12, 15, 17, 18]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
# Функция для поиска `k` элементов, ближайших к `target`, в отсортированном массиве целых чисел `nums` def findKClosestElements(nums, k, target): left = 0 right = len(nums) – 1 while right – left >= k: if abs(nums[left] – target) > abs(nums[right] – target): left = left + 1 else: right = right – 1 return nums[left:left + k] if __name__ == ‘__main__’: nums = [10, 12, 15, 17, 18, 20, 25] target = 16 k = 4 print(findKClosestElements(nums, k, target)) |
Скачать Выполнить код
результат:
[12, 15, 17, 18]
Временная сложность приведенного выше решения равна O(n) и не требует дополнительного места.
Профи
(955),
закрыт
2 года назад
Хлебушек
Оракул
(72700)
2 года назад
Можн примерно так:
find_x = 200 // или float(input())
i = 0
while i < len(x):
if x[i] >= find_x:
break
i +=1
print(f”x = {x[i – 1]}, {x[i]}”)
print(f”y = {y[i – 1]}, {y[i]}”)
Но некоторые моменты решай сам:
– Что если ввести число меньше, чем есть в массиве или больше?
– Поиск можно немного оптимизировать бинарным поиском (отсечь часть, меньше или больше медианы, ведь массив судя по всему отсортирован)
– А если будет число равное 200? Какой диапазон брать? после 200 или до 200?
Тык ПыкМыслитель (7325)
2 года назад
А первая строка зачем? Извиняюсь.
Ну, и предлагать f строки всем – это не очень.
Тык ПыкМыслитель (7325)
2 года назад
А Питон не могу установить. требует КБ МС, КБ сейчас недоступен, доступен только в каком-то кумулятиве. И, ни хрена не помогает даже эта установка. причём я уже отвязался от домена, обнулил пасс Админа, стал локальным админом..
Тык ПыкМыслитель (7325)
2 года назад
Ну, проблема в kb MS – обновлениях безопасности. К программированию это мало относиться, но влияет сильно.
Тык Пык
Мыслитель
(7325)
2 года назад
Самый тупой вариант – сделать сначала 2 переменных. И перебирать, меняя обе переменные.
Можно сделать сортировку списком. С индексами можно разобраться.
Не очень понятно условие “соответствующие им ячейки по y”.
Т. е. списки заведомо одинаковы по длине? И ищем по индексу найденной величины из списка Х индексы (x-1) и (x+1)? Bkb rfr&
Тык ПыкМыслитель (7325)
2 года назад
Я имею в иду не отступления. Я имею в виду, что список уже упорядочен от мин элемента до мах по возрастанию?
Если так, то бери в начале переменную “к”,например, присваивай ей твою величину (200 в примере).
Потом циклом условия перебирай список на то, что очередной элемент списка >к.
Как условие выполнится, выводи из обоих списков величины с индексами “к” и “к-1”.
Это самое тупое и простое решение.. Но, я и не программист)))
Aleks Nots
Просветленный
(21704)
2 года назад
x = [166.3, 188.9, 195.2, 209.1, 219.2, 225, 236.1, 242.8, 247.6, 252.9, 260.6, 265.9, 271.6, 275.5]
y = [0.11, 0.22, 0.33, 0.44, 0.55, 0.65, 0.76, 0.87, 0.98, 1.09, 1.2, 1.31, 1.42, 1.53]
z = float(input())
for i,a in enumerate(x):
~~~~if a > z:
~~~~~~~~break
if i > 0 and i < len(x)-1:
~~~~print(x[i-1], x[i])
~~~~print(y[i-1], y[i])
else:
~~~~print(x[i])
~~~~print(y[i])
Cat BlueПрофи (955)
2 года назад
Тоже благодарю, работает.
Как правильно понимать for i,a in enumerate(x):?
i – индекс, a – итерации?
