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

Дан отсортированный массив целых чисел, найти 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) и не требует дополнительного места.

Источник

Given a sorted array arr[] and a value X, find the k closest elements to X in arr[].

Examples:

Input: K = 4, X = 35
       arr[] = {12, 16, 22, 30, 35, 39, 42, 
               45, 48, 50, 53, 55, 56}
Output: 30 39 42 45

Note that if the element is present in array, then it should not be in output, only the other closest elements are required.

In the following solutions, it is assumed that all elements of array are distinct.

A simple solution is to do linear search for k closest elements.

Start from the first element and search for the crossover point (The point before which elements are smaller than or equal to X and after which elements are greater). This step takes O(n) time.

Once we find the crossover point, we can compare elements on both sides of crossover point to print k closest elements. This step takes O(k) time.

The time complexity of the above solution is O(n).

An Optimized Solution is to find k elements in O(Logn + k) time. The idea is to use Binary Search to find the crossover point. Once we find index of crossover point, we can print k closest elements in O(k) time.

C++

#include<stdio.h>

int findCrossOver(int arr[], int low, int high, int x)

{

if (arr[high] <= x)

return high;

if (arr[low] > x)

return low;

int mid = (low + high)/2;

if (arr[mid] <= x && arr[mid+1] > x)

return mid;

if(arr[mid] < x)

return findCrossOver(arr, mid+1, high, x);

return findCrossOver(arr, low, mid - 1, x);

}

void printKclosest(int arr[], int x, int k, int n)

{

int l = findCrossOver(arr, 0, n-1, x);

int r = l+1;

int count = 0;

if (arr[l] == x) l--;

while (l >= 0 && r < n && count < k)

{

if (x - arr[l] < arr[r] - x)

printf("%d ", arr[l--]);

else

printf("%d ", arr[r++]);

count++;

}

while (count < k && l >= 0)

printf("%d ", arr[l--]), count++;

while (count < k && r < n)

printf("%d ", arr[r++]), count++;

}

int main()

{

int arr[] ={12, 16, 22, 30, 35, 39, 42,

45, 48, 50, 53, 55, 56};

int n = sizeof(arr)/sizeof(arr[0]);

int x = 35, k = 4;

printKclosest(arr, x, 4, n);

return 0;

}

Java

class KClosest

{

int findCrossOver(int arr[], int low, int high, int x)

{

if (arr[high] <= x)

return high;

if (arr[low] > x)

return low;

int mid = (low + high)/2;

if (arr[mid] <= x && arr[mid+1] > x)

return mid;

if(arr[mid] < x)

return findCrossOver(arr, mid+1, high, x);

return findCrossOver(arr, low, mid - 1, x);

}

void printKclosest(int arr[], int x, int k, int n)

{

int l = findCrossOver(arr, 0, n-1, x);

int r = l+1;

int count = 0;

if (arr[l] == x) l--;

while (l >= 0 && r < n && count < k)

{

if (x - arr[l] < arr[r] - x)

System.out.print(arr[l--]+" ");

else

System.out.print(arr[r++]+" ");

count++;

}

while (count < k && l >= 0)

{

System.out.print(arr[l--]+" ");

count++;

}

while (count < k && r < n)

{

System.out.print(arr[r++]+" ");

count++;

}

public static void main(String args[])

{

KClosest ob = new KClosest();

int arr[] = {12, 16, 22, 30, 35, 39, 42,

45, 48, 50, 53, 55, 56

};

int n = arr.length;

int x = 35, k = 4;

ob.printKclosest(arr, x, 4, n);

}

Python3

def findCrossOver(arr, low, high, x) :

if (arr[high] <= x) :

return high

if (arr[low] > x) :

return low

mid = (low + high) // 2

if (arr[mid] <= x and arr[mid + 1] > x) :

return mid

if(arr[mid] < x) :

return findCrossOver(arr, mid + 1, high, x)

return findCrossOver(arr, low, mid - 1, x)

def printKclosest(arr, x, k, n) :

l = findCrossOver(arr, 0, n - 1, x)

r = l + 1

count = 0

if (arr[l] == x) :

l -= 1

while (l >= 0 and r < n and count < k) :

if (x - arr[l] < arr[r] - x) :

print(arr[l], end = " ")

l -= 1

else :

print(arr[r], end = " ")

r += 1

count += 1

while (count < k and l >= 0) :

print(arr[l], end = " ")

l -= 1

count += 1

while (count < k and r < n) :

print(arr[r], end = " ")

r += 1

count += 1

if __name__ == "__main__" :

arr =[12, 16, 22, 30, 35, 39, 42,

45, 48, 50, 53, 55, 56]

n = len(arr)

x = 35

k = 4

printKclosest(arr, x, 4, n)

C#

using System;

class GFG {

static int findCrossOver(int []arr, int low,

int high, int x)

{

if (arr[high] <= x)

return high;

if (arr[low] > x)

return low;

int mid = (low + high)/2;

if (arr[mid] <= x && arr[mid+1] > x)

return mid;

if(arr[mid] < x)

return findCrossOver(arr, mid+1,

high, x);

return findCrossOver(arr, low, mid - 1, x);

}

static void printKclosest(int []arr, int x,

int k, int n)

{

int l = findCrossOver(arr, 0, n-1, x);

int r = l + 1;

int count = 0;

if (arr[l] == x) l--;

while (l >= 0 && r < n && count < k)

{

if (x - arr[l] < arr[r] - x)

Console.Write(arr[l--]+" ");

else

Console.Write(arr[r++]+" ");

count++;

}

while (count < k && l >= 0)

{

Console.Write(arr[l--]+" ");

count++;

}

while (count < k && r < n)

{

Console.Write(arr[r++] + " ");

count++;

}

public static void Main()

{

int []arr = {12, 16, 22, 30, 35, 39, 42,

45, 48, 50, 53, 55, 56};

int n = arr.Length;

int x = 35;

printKclosest(arr, x, 4, n);

}

PHP

<?php

function findCrossOver($arr, $low,

$high, $x)

{

if ($arr[$high] <= $x)

return $high;

if ($arr[$low] > $x)

return $low;

$mid = ($low + $high)/2;

if ($arr[$mid] <= $x and

$arr[$mid + 1] > $x)

return $mid;

if($arr[$mid] < $x)

return findCrossOver($arr, $mid + 1,

$high, $x);

return findCrossOver($arr, $low,

$mid - 1, $x);

}

function printKclosest($arr, $x, $k, $n)

{

$l = findCrossOver($arr, 0, $n - 1, $x);

$r = $l + 1;

$count = 0;

if ($arr[$l] == $x) $l--;

while ($l >= 0 and $r < $n

and $count < $k)

{

if ($x - $arr[$l] < $arr[$r] - $x)

echo $arr[$l--]," ";

else

echo $arr[$r++]," ";

$count++;

}

while ($count < $k and $l >= 0)

echo $arr[$l--]," "; $count++;

while ($count < $k and $r < $n)

echo $arr[$r++]; $count++;

}

$arr =array(12, 16, 22, 30, 35, 39, 42,

45, 48, 50, 53, 55, 56);

$n = count($arr);

$x = 35; $k = 4;

printKclosest($arr, $x, 4, $n);

?>

Javascript

<script>

function findCrossOver(arr, low, high, x)

{

if (arr[high] <= x)

return high

if (arr[low] > x)

return low

var mid = (low + high)

if (arr[mid] <= x && arr[mid + 1] > x)

return mid

if (arr[mid] < x)

return findCrossOver(arr, mid + 1, high, x)

return findCrossOver(arr, low, mid - 1, x)

}

function printKclosest(arr, x, k, n)

{

var l = findCrossOver(arr, 0, n - 1, x)

var r = l + 1

var count = 0

if (arr[l] == x)

l -= 1

while (l >= 0 && r < n && count < k)

{

if (x - arr[l] < arr[r] - x)

{

document.write(arr[l] + " ")

l -= 1

}

else

{

document.write(arr[r] + " ")

r += 1

}

count += 1

}

while (count < k && l >= 0)

{

print(arr[l])

l -= 1

count += 1

}

while (count < k && r < n)

{

print(arr[r])

r += 1

count += 1

}

var arr = [ 12, 16, 22, 30, 35, 39, 42,

45, 48, 50, 53, 55, 56 ]

var n = arr.length

var x = 35

var k = 4

printKclosest(arr, x, 4, n)

</script>

Time complexity: O(Logn + k).
Auxiliary Space: O(1), since no extra space has been used.

Approach 2: Using Priority Queue

This approach uses a priority queue (max heap) to maintain the k closest numbers to x. It iterates over the elements in the array and calculates their absolute differences from x. The pairs of absolute differences and negative values are pushed into the max heap. If the size of the max heap exceeds k, the element with the maximum absolute difference is removed. Finally, the top k elements from the max heap are extracted and stored in a result vector. The vector is then reversed to obtain the closest numbers in ascending order before being returned as the result.

Below is the implementation:

C++

#include <bits/stdc++.h>

using namespace std;

vector<int> findClosestElements(vector<int>& arr, int k,

int x)

{

priority_queue<pair<int, int> > maxH;

int n = arr.size();

for (int i = 0; i < n; i++) {

if (arr[i] == x)

continue;

maxH.push({ abs(arr[i] - x), -arr[i] });

if (maxH.size() > k)

maxH.pop();

}

vector<int> result;

while (!maxH.empty()) {

auto p = maxH.top();

maxH.pop();

result.push_back(-p.second);

}

reverse(result.begin(), result.end());

return result;

}

int main()

{

vector<int> arr = { 12, 16, 22, 30, 35, 39, 42,

45, 48, 50, 53, 55, 56 };

int k = 4, x = 35;

vector<int> res = findClosestElements(arr, k, x);

for (int i = 0; i < res.size(); i++) {

cout << res[i] << " ";

}

cout << endl;

return 0;

}

Time Complexity: O(n log k), where n is the size of the array and k is the number of elements to be returned. The priority queue takes O(log k) time to insert an element and O(log k) time to remove the top element. Therefore, traversing through the array and inserting elements into the priority queue takes O(n log k) time. Popping elements from the priority queue and pushing them into the result vector takes O(k log k) time. Therefore, the total time complexity is O(n log k + k log k) which is equivalent to O(n log k).
Auxiliary Space: O(k), as we are using a priority queue of size k+1 and a vector of size k to store the result.

Exercise: Extend the optimized solution to work for duplicates also, i.e., to work for arrays where elements don’t have to be distinct.

Last Updated :
25 May, 2023

Like Article

Save Article

Источник

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

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

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)

Источник

Раз отсортирован, значит надо просто идти подряд, пока не найдётся элемент, превышающий заданные значения. Вернуть предыдущий.

function nearest( $sample, $arr) {
  $found = false;
  foreach( $arr AS $row) {
    if($row[0] <= $sample[0]  &&  $row[1] <= $sample[1]  &&  $row[2] <= $sample[2]) $found = $row;
    else break;
  }
  
  return $found;
}

$data = [
  [1, 1, 1],
  [1, 2, 1],
  [1, 2, 2],
  [1, 5, 4],
  [1, 5, 6],
  [2, 1, 6],
  [2, 2, 2],
];

echo implode(',', nearest( [1,5,5], $data)); //  1,5,4

Источник