658. Find K Closest Elements

LeetCode easy оригинал: C# #array #csharp #easy #leetcode #search #sliding-window #sort #two-pointers

LeetCode Static

Дан отсортированный массив целых чисел arr, два целых числа k и x. Верните k ближайших к x целых чисел в массиве. Результат также должен быть отсортирован в порядке возрастания.

Целое число a ближе к x, чем целое число b, если:

|a - x| < |b - x|, или

|a - x| == |b - x| и a < b.

Пример

Input: arr = [1,2,3,4,5], k = 4, x = 3

Output: [1,2,3,4]

C# решение

сопоставлено/оригинал

public class Solution {
    public IList<int> FindClosestElements(int[] arr, int k, int x) {
        int left = 0, right = arr.Length - k;
        while (left < right) {
            int mid = (left + right) / 2;
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return arr.Skip(left).Take(k).ToList();
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int> FindClosestElements(vector<int>& arr, int k, int x) {
        int left = 0, right = arr.size() - k;
        while (left < right) {
            int mid = (left + right) / 2;
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return arr.Skip(left).Take(k).ToList();
    }
}

Java решение

auto-draft, проверить перед отправкой

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public List<int> FindClosestElements(int[] arr, int k, int x) {
        int left = 0, right = arr.length - k;
        while (left < right) {
            int mid = (left + right) / 2;
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return arr.Skip(left).Take(k).ToList();
    }
}

Python решение

сопоставлено/оригинал

import bisect

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        pos = bisect.bisect_left(arr, x)
        left, right = pos - 1, pos
        
        while right - left - 1 < k:
            if left == -1:
                right += 1
            elif right == len(arr) or (x - arr[left] <= arr[right] - x):
                left -= 1
            else:
                right += 1
        
        return arr[left + 1:right]

Go решение

сопоставлено/оригинал

func findClosestElements(arr []int, k int, x int) []int {
    left, right := 0, len(arr) - k

    for left < right {
        mid := (left + right) / 2
        if x - arr[mid] > arr[mid + k] - x {
            left = mid + 1
        } else {
            right = mid
        }
    }

    return arr[left:left + k]
}

Algorithm

Бинарный поиск:

Найдите положение числа x или ближайшего к нему числа в массиве arr с помощью бинарного поиска.

Два указателя:

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

Сортировка:

Отсортируйте итоговый список, если это необходимо (в данном случае это не нужно, так как массив уже отсортирован).

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.