План курса / Все задачи / Алгоритмы и структуры данных
К ближайших чисел
легко
Дан массив nums, отсортированный в неубывающем порядке, индекс idx и число k. Нужно найти k ближайших к значению nums[idx] чисел в массиве и вернуть в любом порядке. При равных расстояниях предпочтение отдаётся меньшим числам.
Пример 1:
Ввод: nums = [2,5,5,5,8], idx = 2, k = 4
Вывод: [2,5,5,5]
Объяснение: ответ [2,5,5,5], а не [5,5,5,8], потому что 2 < 8 при abs(8-5) = abs(2-5)
Ожидается, что ответ - новый массив, а не модификация текущего или слайс от nums
public class Solution {
public static List<int> FindNearestNumbers(List<int> nums, int idx, int k) {
if (k == 0) {
return new List<int>();
}
// добавляем в ответ nums[idx]
List<int> result = new List<int> { nums[idx] };
// l - индекс кандидата на добавление слева от idx
// r - индекс кандидата на добавление справа от idx
int l = idx - 1, r = idx + 1;
for (int _ = 0; _ < k - 1; _++) {
if (r >= nums.Count || (l >= 0 && Math.Abs(nums[idx] - nums[l]) <= Math.Abs(nums[idx] - nums[r]))) {
result.Add(nums[l]);
l--;
} else {
result.Add(nums[r]);
r++;
}
}
return result;
}
}
#include <vector>
#include <cmath>
using namespace std;
vector<int> findNearestNumbers(vector<int> nums, int idx, int k) {
if (k == 0) {
return {};
}
// добавляем в ответ nums[idx]
vector<int> result = {nums[idx]};
// l - индекс кандидата на добавление слева от idx
// r - индекс кандидата на добавление справа от idx
int l = idx - 1, r = idx + 1;
for (int i = 0; i < k - 1; ++i) {
if (r >= nums.size() || (l >= 0 && abs(nums[idx] - nums[l]) <= abs(nums[idx] - nums[r]))) {
result.push_back(nums[l]);
--l;
} else {
result.push_back(nums[r]);
++r;
}
}
return result;
}
package main
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func findNearestNumbers(nums []int, idx int, k int) []int {
if k == 0 {
return []int{}
}
// добавляем в ответ nums[idx]
result := []int{nums[idx]}
// l - индекс кандидата на добавление слева от idx
// r - индекс кандидата на добавление справа от idx
l, r := idx-1, idx+1
for i := 0; i < k-1; i++ {
if r >= len(nums) || (l >= 0 && abs(nums[idx]-nums[l]) <= abs(nums[idx]-nums[r])) {
result = append(result, nums[l])
l--
} else {
result = append(result, nums[r])
r++
}
}
return result
}
import java.util.*;
public class Solution {
public List<Integer> findNearestNumbers(List<Integer> nums, Integer idx, Integer k) {
if (k == 0) {
return new ArrayList<>();
}
// добавляем в ответ nums[idx]
List<Integer> result = new ArrayList<>();
result.add(nums.get(idx));
// l - индекс кандидата на добавление слева от idx
// r - индекс кандидата на добавление справа от idx
int l = idx - 1, r = idx + 1;
for (int i = 0; i < k - 1; i++) {
if (r >= nums.size() || (l >= 0 && Math.abs(nums.get(idx) - nums.get(l)) <= Math.abs(nums.get(idx) - nums.get(r)))) {
result.add(nums.get(l));
l--;
} else {
result.add(nums.get(r));
r++;
}
}
return result;
}
}
from typing import *
def find_nearest_numbers(nums: List[int], idx: int, k: int) -> List[int]:
if k == 0:
return []
# добавляем в ответ nums[idx]
result = [nums[idx]]
# l - индекс кандидата на добавление слева от idx
# r - индекс кандидата на добавление справа от idx
l, r = idx - 1, idx + 1
for _ in range(k - 1):
if r >= len(nums) or l >= 0 and abs(nums[idx] - nums[l]) <= abs(nums[idx] - nums[r]):
result.append(nums[l])
l -= 1
else:
result.append(nums[r])
r += 1
return result
/**
* @param {number[]} nums
* @param {number} idx
* @param {number} k
* @returns {number[]}
*/
export function findNearestNumbers(nums, idx, k) {
if (k === 0) {
return [];
}
// добавляем в ответ nums[idx]
const result = [nums[idx]];
// l - индекс кандидата на добавление слева от idx
// r - индекс кандидата на добавление справа от idx
let l = idx - 1, r = idx + 1;
for (let i = 0; i < k - 1; i++) {
if (r >= nums.length || (l >= 0 && Math.abs(nums[idx] - nums[l]) <= Math.abs(nums[idx] - nums[r]))) {
result.push(nums[l]);
l--;
} else {
result.push(nums[r]);
r++;
}
}
return result;
}