Как найти ближайший элемент массива к числу - Исправление недочетов и поиск решений вместе с Examum.ru

Для неотсортированного массива. Для отсортированного лучше использовать бинпоиск.

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

Источник

Дан отсортированный массив целых чисел, найти 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

#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++

#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

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

# Функция для поиска в указанном массиве `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

#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

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

# Функция для поиска `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) и не требует дополнительного места.

Источник

I have an Array of integers in javascript, [5,10,15,20,25,30,35]
when given a number x, how can I find the element in the array that is closest to that number?

If the number is over a value, but less than halfway to the next number, I would choose the smaller value, if it were over halfway to the next number, I would choose the higher number.

For example 7 would return 5, but 8 would return 10. How can I accomplish this? Any help or tips would be appreciated. I have searched and cannot find a solution. I’m sure this is sort of common.

Aurelio

24.4k9 gold badges58 silver badges63 bronze badges

asked Jan 26, 2011 at 23:53

HcabnettekHcabnettek

12.6k38 gold badges124 silver badges190 bronze badges

Probably the easiest thing to do is sort based on distance from the reference value x, and then take the first item.

The built-in Array.prototype.sort() can take a comparison function which will be called for pairs of values from the array. Then the key is simply to pass in a comparison function which compares the two values based on their distance from the reference value x.

let x = 8;
let array = [5, 10, 15, 20, 25, 30, 35];
let closest = array.sort( (a, b) => Math.abs(x - a) - Math.abs(x - b) )[0];

See this simple demo.

answered Oct 16, 2015 at 20:46

function getClosest(array, target) {
    var tuples = _.map(array, function(val) {
        return [val, Math.abs(val - target)];
    });
    return _.reduce(tuples, function(memo, val) {
        return (memo[1] < val[1]) ? memo : val;
    }, [-1, 999])[0];
}

If using a functional approach is applicable then you can map the set to tuples of (value, distance) then reduce that set of tuples to the tuple with the smallest distance. We return the value in that tuple.

To explain the useage of _.map. You map all the values in your array to new values and the function will return the array of new values. In this case an array of tuples.

To explain the useage of _.reduce. You reduce the array to a single value. You pass in an array and a memo. The memo is your «running counter» as you move through the array. In this case we check whether the current tuple is closer then the memo and if so make it the memo. We then return the memo at the end.

The code snippet above relies on underscore.js to remove the nitty gritty of functional style javascript

answered Jan 27, 2011 at 0:30

RaynosRaynos

166k56 gold badges350 silver badges396 bronze badges

Your example list is sorted. If this is always the case, then binary search for your number. If you don’t find the exact number, make the binary search end off by checking the two numbers around where the number would be and return the closest. Be careful with edge cases where all numbers are greater or are all smaller than the target number

If the list isn’t always sorted, then go through the list keeping track of the largest number <= the target number and the smallest number >= the target number. Return the one that’s closest to the target.

In either solution, you’ll need to decide which side to favour if for example you’re searching for 2 in [1, 3].

answered Jan 26, 2011 at 23:58

moinudinmoinudin

133k45 gold badges189 silver badges214 bronze badges

Create a temporary array of the same size as your original array, and populate it with the differences between your x and the array element.

For example, let the temporary array be temp[], and your original array be a[]:

temp[i]=Math.abs(x-a[i]);

Then, return the index of the minimum value in temp[] to the user.

answered Jan 27, 2011 at 0:11

Arjun J RaoArjun J Rao

9151 gold badge10 silver badges25 bronze badges

Assuming the array is sorted, step through each adjacent pair of integers in the array. For each pair (say «5 and 10» or «20 and 25»), test if x is in between them, and if so, return whichever one is closer to x (with a bias towards the lower one).

You would also need a special case for when x is less than the first number (return the first number) or greater than the last number (return the last number).

If the array is not sorted, sort it first.

answered Jan 26, 2011 at 23:56

mgiucamgiuca

20.8k6 gold badges53 silver badges70 bronze badges

I created my own function since i could not find any that meets my requeriments.

    function closest_number(quantities, number, closest_factor)
    {
        if (closest_factor == 'ceil')
        {
            quantities.sort(function(a, b)
                {
                    return a - b
                }
            );

            for (var i = 0; i < quantities.length; i++)
            {
                if (quantities[i] >= number)
                {
                    return quantities[i];
                }

                last_value = quantities[i];
            }

            return last_value;
        }
        else if (closest_factor == 'floor')
        {
            quantities.sort(function(a, b)
                {
                    return a - b
                }
            );

            min_value = quantities[0];

            for (var i = 0; i < quantities.length; i++)
            {
                if (number == quantities[i])
                {
                    return number;
                }
                else if (quantities[i] < number)
                {
                    min_value = quantities[i];
                }
                else if(quantities[i] > number)
                {
                    return min_value;
                }           
            }

            return min_value;
        }
        else
        {
            return false;
        }
    };

answered Oct 27, 2012 at 10:37

Since Array.reduce is a reality for so long (even IE9 supports it), the problem is easily solvable with it. This way, no need to sort the array first (no array mutation at all):

var numbers = [20, 25, 30, 35, 5, 10, 15], x = 7;

var output = numbers.reduce(function (prev, curr) {
  return Math.abs(curr - x) < Math.abs(prev - x) ? curr : prev
});

console.log(output);

You can go further and solve it with only one line of ES6 (ECMAScript 2015) syntax, by using an arrow function (but with no IE support in this case):

const numbers = [20, 25, 30, 35, 5, 10, 15], x = 7;

const output = numbers.reduce((prev, curr) => Math.abs(curr - x) < Math.abs(prev - x) ? curr : prev);

console.log(output);

Of course, for flexibility and reusability, it’s easy to make it as a function:

const closest = (array, goal) => array.reduce((prev, curr) => Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);

console.log(closest([20, 25, 30, 35, 5, 10, 15], 7));
console.log(closest([20, 25, 30, 35, 5, 10, 15], 8));
console.log(closest([1, 5, 7], -5));
console.log(closest([1, 5, 7], 4));
console.log(closest([1, 5, 7], 20));

answered Nov 5, 2020 at 21:14

Erick PetrucelliErick Petrucelli

14.2k8 gold badges63 silver badges84 bronze badges

Источник

Напишите программу, которая находит в массиве элемент, самый близкий по величине к данному числу.

Входные данные

В первой строке содержатся список чисел — элементы массива (целые числа, не превосходящие 1000

по абсолютному значению).

Во второй строке вводится одно целое число x
, не превосходящее 1000

по абсолютному значению.

Выходные данные

Вывести значение элемента массива, ближайшего к x
. Если таких чисел несколько, выведите любое из них.

Python

a, n, find_num = [int(i) for i in input().split()], int(input()), 100
for i in range(len(a)):
    if a[i] < n:
        find_num = -find_num
    else:
        find_num = find_num + 0
    if a[i] >= n and a[i] - n <= find_num - n:
        find_num = a[i]
    elif a[i] <= n and find_num - n <= a[i] - n:
        find_num = a[i]
print(find_num)

Источник

Permalink

Cannot retrieve contributors at this time

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters

Show hidden characters

	# Напишите программу, которая находит в массиве элемент, самый близкий по величине к данному числу.

	l = input()
	numbers = list(map(int, input().strip().split()))
	x = int(input().strip())

	res = numbers[0]
	for i in numbers:
	if abs(i — x) < abs(res — x):
	res = i

	print(res)

Источник