Ввод: nums = [2,3,3,4,5,6,7], target = 3, k = 3
Вывод: [2,3,3]
Объяснение: 4 > 2, поэтому берем [2,3,3], а не [3,3,4]
Ограничения:
len(nums) >= 1
Решение (не оптимальное, но его принимают)
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static List<int> Search(List<int> nums, int target, int k)
{
// находим позицию, куда вставился бы target
int insertPos = nums.BinarySearch(target);
if (insertPos < 0) insertPos = ~insertPos;
// определяем границы окна размером ~2k вокруг позиции target
int windowStart = Math.Max(0, insertPos - k);
int windowEnd = Math.Min(nums.Count, insertPos + k + 1);
// создаём пары (расстояние до target, значение элемента)
var candidates = new List<(int dist, int val)>();
for (int i = windowStart; i < windowEnd; i++)
{
candidates.Add((Math.Abs(nums[i] - target), nums[i]));
}
// сортируем по расстоянию (при равных — по значению)
candidates.Sort((a, b) => a.dist != b.dist ? a.dist.CompareTo(b.dist) : a.val.CompareTo(b.val));
// берём k ближайших и сортируем по значению для вывода
var result = candidates.Take(k).Select(item => item.val).ToList();
result.Sort();
return result;
}
}
#include <vector>
#include <algorithm>
using namespace std;
vector<int> search(vector<int> nums, int target, int k) {
// находим позицию, куда вставился бы target
auto it = lower_bound(nums.begin(), nums.end(), target);
size_t insertPos = distance(nums.begin(), it);
// определяем границы окна размером ~2k вокруг позиции target
size_t windowStart = insertPos >= k ? insertPos - k : 0;
size_t windowEnd = insertPos + k + 1 <= nums.size() ? insertPos + k + 1 : nums.size();
// создаём пары (расстояние до target, значение элемента)
vector<pair<int, int>> candidates(windowEnd - windowStart);
for (size_t i = windowStart; i < windowEnd; ++i) {
candidates[i - windowStart] = {abs(nums[i] - target), nums[i]};
}
// сортируем по расстоянию (при равных — по значению)
sort(candidates.begin(), candidates.end());
// берём k ближайших
vector<int> result;
result.reserve(k);
transform(
candidates.begin(), candidates.begin() + k, back_inserter(result),
[](const auto& item) { return item.second; }
);
// сортируем по значению для вывода
sort(result.begin(), result.end());
return result;
}
package main
import "sort"
func search(nums []int, target int, k int) []int {
// находим позицию, куда вставился бы target
insertPos := sort.SearchInts(nums, target)
// определяем границы окна размером ~2k вокруг позиции target
windowStart := 0
if insertPos >= k {
windowStart = insertPos - k
}
windowEnd := len(nums)
if insertPos+k+1 < len(nums) {
windowEnd = insertPos + k + 1
}
// создаём пары (расстояние до target, значение элемента)
type candidate struct{ dist, val int }
candidates := make([]candidate, 0, windowEnd-windowStart)
for i := windowStart; i < windowEnd; i++ {
dist := nums[i] - target
if dist < 0 {
dist = -dist
}
candidates = append(candidates, candidate{dist, nums[i]})
}
// сортируем по расстоянию (при равных — по значению)
sort.Slice(candidates, func(i, j int) bool {
if candidates[i].dist != candidates[j].dist {
return candidates[i].dist < candidates[j].dist
}
return candidates[i].val < candidates[j].val
})
// берём k ближайших
result := make([]int, k)
for i := 0; i < k; i++ {
result[i] = candidates[i].val
}
// сортируем по значению для вывода
sort.Ints(result)
return result
}
package main
import "sort"
func search(nums []int, target int, k int) []int {
// находим позицию, куда вставился бы target
insertPos := sort.SearchInts(nums, target)
// определяем границы окна размером ~2k вокруг позиции target
windowStart := 0
if insertPos >= k {
windowStart = insertPos - k
}
windowEnd := len(nums)
if insertPos+k+1 < len(nums) {
windowEnd = insertPos + k + 1
}
// создаём пары (расстояние до target, значение элемента)
type candidate struct{ dist, val int }
candidates := make([]candidate, 0, windowEnd-windowStart)
for i := windowStart; i < windowEnd; i++ {
dist := nums[i] - target
if dist < 0 {
dist = -dist
}
candidates = append(candidates, candidate{dist, nums[i]})
}
// сортируем по расстоянию (при равных — по значению)
sort.Slice(candidates, func(i, j int) bool {
if candidates[i].dist != candidates[j].dist {
return candidates[i].dist < candidates[j].dist
}
return candidates[i].val < candidates[j].val
})
// берём k ближайших
result := make([]int, k)
for i := 0; i < k; i++ {
result[i] = candidates[i].val
}
// сортируем по значению для вывода
sort.Ints(result)
return result
}
import java.util.*;
public class Solution {
public List<Integer> search(List<Integer> nums, int target, int k) {
// находим позицию, куда вставился бы target
int insertPos = Collections.binarySearch(nums, target);
if (insertPos < 0) insertPos = -insertPos - 1;
// определяем границы окна размером ~2k вокруг позиции target
int windowStart = Math.max(0, insertPos - k);
int windowEnd = Math.min(nums.size(), insertPos + k + 1);
// создаём пары (расстояние до target, значение элемента)
List<int[]> candidates = new ArrayList<>();
for (int i = windowStart; i < windowEnd; i++) {
candidates.add(new int[]{Math.abs(nums.get(i) - target), nums.get(i)});
}
// сортируем по расстоянию (при равных — по значению)
candidates.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
// берём k ближайших
List<Integer> result = new ArrayList<>();
for (int i = 0; i < k; i++) {
result.add(candidates.get(i)[1]);
}
// сортируем по значению для вывода
Collections.sort(result);
return result;
}
}
/**
* Бинарный поиск позиции вставки (аналог bisect_left)
* @param {number[]} nums
* @param {number} target
* @returns {number}
*/
function searchInsertPosition(nums, target) {
// ответ будет находится в элементе указывающим на r
// поэтому сдвигаем l на 1 влево, чтобы r мог принимать
// значения [0, nums.length], то есть от первого индекса
// и до позиции "после последнего" включительно
let l = -1;
let r = nums.length;
while (r - l > 1) {
let m = Math.floor((l + r) / 2);
if (nums[m] < target) {
l = m;
} else {
r = m;
}
}
return r;
}
/**
* @param {number[]} nums
* @param {number} target
* @param {number} k
* @returns {number[]}
*/
export function search(nums, target, k) {
// находим позицию, куда вставился бы target
const insertPos = searchInsertPosition(nums, target);
// определяем границы окна размером ~2k вокруг позиции target
const windowStart = Math.max(0, insertPos - k);
const windowEnd = Math.min(nums.length, insertPos + k + 1);
// создаём пары (расстояние до target, значение элемента)
const candidates = [];
for (let i = windowStart; i < windowEnd; i++) {
candidates.push([Math.abs(nums[i] - target), nums[i]]);
}
// сортируем по расстоянию (при равных — по значению)
candidates.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
// берём k ближайших и сортируем по значению для вывода
const result = candidates.slice(0, k).map(item => item[1]);
result.sort((a, b) => a - b);
return result;
}
Оценка сложности
Время: O(log(n) + k*log(k)), где n - число всех элементов в массиве nums;k - число элементов, которое нужно вернуть
Память: O(k)
Примечание: это решение не является оптимальным по времени — оно работает за O(log(n) + k*log(k)) вместо возможного O(log(n-k)). Однако на собеседовании для этой задачи его принимают (как правило без снижения балов за секцию). Из-за сложности задачи так же обычно разрешают использовать встроенный бинарный поиск (bisect, lower_bound, Collections.binarySearch и т.д.), а написание бинарного поиска вручную может быть предложено как усложнение.
Оптимальное решение приведено ниже, но для его написания требуется глубокое понимание бинарного поиска и без подготовки будет достаточно сложно его понять и объяснить.
Решение (оптимальное)
public class Solution
{
// Немного переформулируем задачу:
// Нас просят найти самую выгодную позицию "плавающего окна",
// в котором K наиболее ближайших элементов к "target".
// Для решения будем использовать бинарный поиск,
// так как можно для каждой позиции окна однозначно сказать,
// выгодно двигать окно вправо или нет.
// Хороший - если подвинуть вправо выгодно.
// Сравниваем nums[i] и nums[i + k], чтобы понять, что ближе к "target".
// Если nums[i] ближе, то нет смысла двигать вправо, так как
// nums[i + k] — элемент, который будет в нашем "плавающем окне",
// если шагнуть вправо.
// Note: nums[i + k] — это именно элемент, который войдет,
// если подвинуть плавающее окно, то есть сейчас он не входит.
// Ответ будет в "right", поэтому изначально left = -1,
// чтобы right мог принимать значения [0, nums.Count - k] включительно.
public static List<int> Search(List<int> nums, int target, int k)
{
if (nums.Count == 0 || k <= 0 || k > nums.Count)
{
return new List<int>(); // Возвращаем пустой список, если входные данные некорректны
}
int left = -1, right = nums.Count - k;
while (right - left > 1)
{
int mid = (left + right) / 2;
// Сравниваем расстояние от target до nums[mid] и nums[mid + k]
if (target - nums[mid] > nums[mid + k] - target)
{
left = mid; // Двигаем левую границу, если выгодно двигать окно вправо
}
else
{
right = mid; // Иначе двигаем правую границу
}
}
// Возвращаем подсписок из k элементов, начиная с позиции right
return nums.GetRange(right, k);
}
}
#include <vector>
using namespace std;
vector<int> search(const vector<int>& nums, int target, int k) {
// немного переформулируем задачу:
// нас просят найти самую выгодную позицию "плавающего окна"
// в котором K наиболее ближайших элементов к "target"
// для решения будем использовать бинарный поиск
// так как можно для каждой позиции окна однозначно сказать выгодно
// двигать окно вправо или нет
// хороший - если подвинуть вправо выгодно
// сравниваем nums[i] и nums[i + k], чтобы понять что ближе к "target"
// если nums[i] ближе, то нет смысла двигать вправо, так как
// nums[i + k] элемент, который будет в нашем "плавающем окне"
// если шагнуть вправо
// Note: nums[i + k] - это именно элемент, который войдет
// если подвинуть плавающее окно, то есть сейчас он не входит
// ответ будет в "r", поэтому изначально l = -1
// чтобы r мог принимать значения [0, len(nums) - k] включительно
int l = -1, r = nums.size() - k;
while (r - l > 1) {
int m = (l + r) / 2;
if (target - nums[m] > nums[m + k] - target) {
l = m;
} else {
r = m;
}
}
return vector<int>(nums.begin() + r, nums.begin() + r + k);
}
package main
func search(nums []int, target int, k int) []int {
// немного переформулируем задачу:
// нас просят найти самую выгодную позицию "плавающего окна"
// в котором K наиболее ближайших элементов к "target"
// для решения будем использовать бинарный поиск
// так как можно для каждой позиции окна однозначно сказать выгодно
// двигать окно вправо или нет
// хороший - если подвинуть вправо выгодно
// сравниваем nums[i] и nums[i + k], чтобы понять что ближе к "target"
// если nums[i] ближе, то нет смысла двигать вправо, так как
// nums[i + k] элемент, который будет в нашем "плавающем окне"
// если шагнуть вправо
// Note: nums[i + k] - это именно элемент, который войдет
// если подвинуть плавающее окно, то есть сейчас он не входит
// ответ будет в "r", поэтому изначально l = -1
// чтобы r мог принимать значения [0, len(nums) - k] включительно
l, r := -1, len(nums)-k
for r-l > 1 {
m := (l + r) / 2
if target-nums[m] > nums[m+k]-target {
l = m
} else {
r = m
}
}
return nums[r : r+k]
}
import java.util.*;
public class Solution {
public List<Integer> search(List<Integer> nums, int target, int k) {
// немного переформулируем задачу:
// нас просят найти самую выгодную позицию "плавающего окна"
// в котором K наиболее ближайших элементов к "target"
// для решения будем использовать бинарный поиск
// так как можно для каждой позиции окна однозначно сказать выгодно
// двигать окно вправо или нет
// хороший - если подвинуть вправо выгодно
// сравниваем nums[i] и nums[i + k] чтобы понять, что ближе к "target"
// если nums[i] ближе, то нет смысла двигать вправо, так как
// nums[i + k] элемент, который будет в нашем "плавающем окне"
// если шагнуть вправо
// Note: nums[i + k] - это именно элемент, который войдет
// если подвинуть плавающее окно, то есть сейчас он не входит
// ответ будет в "r", поэтому изначально l = -1
// чтобы r мог принимать значения [0, len(nums) - k] включительно
int l = -1, r = nums.size() - k;
while (r - l > 1) {
int m = (l + r) / 2;
if (target - nums.get(m) > nums.get(m + k) - target) {
l = m;
} else {
r = m;
}
}
return nums.subList(r, r + k);
}
}
from typing import *
def search(nums: List[int], target: int, k: int) -> List[int]:
# немного переформулируем задачу:
# нас просят найти самую выгодную позицию "плавающего окна"
# в котором K наиболее ближайших элементов к "target"
# для решения будем использовать бинарный поиск
# так как можно для каждой позиции окна однозначно сказать выгодно
# двигать окно вправо или нет
# хороший - если подвинуть вправо выгодно
# сравниваем arr[i] и arr[i + k] чтобы понять, что ближе к "target"
# если arr[i] ближе, то нет смысла двигать вправо, так как
# arr[i + k] элемент, который будет в нашем "плавающем окне"
# если шагнуть вправо
# Note: arr[i + k] - это именно элемент, который войдет
# если подвинуть плавающее окно, то есть сейчас он не входит
# ответ будет в "r", поэтому изначально l = -1
# чтобы r мог принимать значения [0, len(arr) - k] включительно
l, r = -1, len(nums) - k
while r - l > 1:
m = (l + r) // 2
if target - nums[m] > nums[m + k] - target:
l = m
else:
r = m
return nums[r:r+k]
export function search(nums, target, k) {
// немного переформулируем задачу:
// нас просят найти самую выгодную позицию "плавающего окна"
// в котором K наиболее ближайших элементов к "target"
// для решения будем использовать бинарный поиск
// так как можно для каждой позиции окна однозначно сказать выгодно
// двигать окно вправо или нет
// хороший - если подвинуть вправо выгодно
// сравниваем nums[i] и nums[i + k], чтобы понять, что ближе к "target"
// если nums[i] ближе, то нет смысла двигать вправо, так как
// nums[i + k] элемент, который будет в нашем "плавающем окне"
// если шагнуть вправо
// Note: nums[i + k] - это именно элемент, который войдет
// если подвинуть плавающее окно, то есть сейчас он не входит
// ответ будет в "r", поэтому изначально l = -1
// чтобы r мог принимать значения [0, nums.length - k] включительно
let l = -1;
let r = nums.length - k;
while (r - l > 1) {
const m = Math.floor((l + r) / 2);
// проверяем, стоит ли двигать окно вправо
if (target - nums[m] > nums[m + k] - target) {
l = m;
} else {
r = m;
}
}
// возвращаем k ближайших элементов начиная с индекса r
return nums.slice(r, r + k);
}
Оценка сложности
Время: O(log(n-k)), где n - число всех элементов в массиве nums;k - число элементов, которое нужно вернуть