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
Напишите программу, которая находит в массиве элемент, самый близкий по величине к данному числу.
Входные данные
В первой строке содержатся список чисел — элементы массива (целые числа, не превосходящие 1000
по абсолютному значению).
Во второй строке вводится одно целое число x
, не превосходящее 1000
по абсолютному значению.
Выходные данные
Вывести значение элемента массива, ближайшего к x
. Если таких чисел несколько, выведите любое из них.
| Python | ||
|
Вот решение, которое я нашел (если кому понадобится в будущем):
/**
* @param {Array} settings.arr
* @param {Number} settings.valueToFind
* @param {Function} settings.comparator
*
* @returns {Number|undefined}
*/
function findClosest(settings) {
var lo = -Infinity,
hi = Infinity,
arr = settings.arr,
valueToFind = settings.valueToFind,
comparator = settings.comparator,
result;
for (var i = 0; i < arr.length; i++) {
if (arr[i] <= valueToFind && arr[i] >= lo) {
lo = arr[i];
continue;
}
if (arr[i] >= valueToFind && arr[i] <= hi) {
hi = arr[i];
}
}
result = comparator(lo, hi, valueToFind);
return isFinite(result) ? result : undefined; // or false
}Вот так выглядит объект settings c четырьмя возможными компараторами:
var comparator1 = function(lo, hi, valueToFind) {
return lo; // or hi
};
var comparator2 = function(lo, hi, valueToFind) {
var result = lo; // or hi
switch (true) {
case valueToFind - lo < hi - valueToFind:
result = lo;
break;
case valueToFind - lo > hi - valueToFind:
result = hi;
break;
}
return result;
};
var settings = {
arr: [1, 5, 10, 8, 5, 13],
valueToFind: 7,
comparator: comparator2
};И сам вызов функции:
alert(findClosest(settings));
PS:
Вместо false, в случае когда результат не определен, я решил возвращать undefined, так как это значение ближе по семантике.
Дан отсортированный массив целых чисел, найти 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) и не требует дополнительного места.