В этой статье мы рассмотрим различные методы поиска K ближайших чисел в отсортированном массиве. Эта проблема обычно встречается во многих сценариях, таких как поиск K ближайших соседей или выбор K наиболее похожих элементов. Мы рассмотрим несколько подходов, предоставив разговорные объяснения и примеры кода, которые помогут вам понять и эффективно реализовать эти методы.

Метод 1: двоичный поиск и техника скользящего окна
Для начала мы можем использовать алгоритм двоичного поиска, чтобы найти элемент, ближайший к целевому номеру X. Найдя этот элемент, мы можем сформировать вокруг него скользящее окно., расширяясь влево или вправо в зависимости от близости к X. Поддерживая размер окна K, мы можем эффективно идентифицировать K ближайших чисел в массиве.

Вот реализация этого метода на Python:

def find_k_closest_numbers(arr, K, X):
    left = 0
    right = len(arr) - 1
    closest_index = binary_search(arr, X)

    while right - left + 1 > K:
        if abs(arr[left] - X) > abs(arr[right] - X):
            left += 1
        else:
            right -= 1

    return arr[left:right+1]
def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    if left == 0:
        return 0
    elif left == len(arr):
        return len(arr) - 1
    else:
        return left if abs(arr[left] - target) < abs(arr[left - 1] - target) else left - 1

Метод 2: подход с двумя указателями
Другой эффективный подход — использование метода двух указателей. Мы можем инициализировать два указателя: один в начале массива, а другой в конце. Мы сравниваем абсолютные различия между числами, на которые указывают два указателя, и целевым числом X. На основе разницы мы перемещаем указатели ближе друг к другу, пока не получим K ближайших чисел.

Вот реализация этого метода на Python:

def find_k_closest_numbers(arr, K, X):
    left = 0
    right = len(arr) - 1

    while right - left + 1 > K:
        if abs(arr[left] - X) > abs(arr[right] - X):
            left += 1
        else:
            right -= 1

    return arr[left:right+1]

Метод 3: очередь приоритетов (куча)
Мы также можем решить эту проблему, используя очередь приоритетов, обычно реализуемую как структуру данных кучи. Мы начинаем с инициализации максимальной кучи первыми K элементами отсортированного массива, отсортированными на основе их абсолютных отличий от целевого числа X. Затем мы перебираем оставшиеся элементы массива, сравнивая их различия с верхним элементом в массиве. куча. Если текущий элемент ближе к X, мы заменяем верхний элемент в куче и корректируем его соответствующим образом.

Вот реализация этого метода на Python с использованием модуля heapq:

import heapq
def find_k_closest_numbers(arr, K, X):
    max_heap = []

    for num in arr[:K]:
        heapq.heappush(max_heap, (-abs(num - X), num))

    for num in arr[K:]:
        diff = abs(num - X)
        if diff < -max_heap[0][0]:
            heapq.heappop(max_heap)
            heapq.heappush(max_heap, (-diff, num))

    return [num for _, num in max_heap]

В этой статье мы рассмотрели три различных метода поиска K ближайших чисел в отсортированном массиве. Мы рассмотрели технику двоичного поиска и скользящего окна, подход с двумя указателями и метод очереди с приоритетами (кучи). Каждый метод предлагает уникальное решение проблемы, и выбор метода зависит от конкретных требований и ограничений вашего приложения. Поняв эти методы и реализовав их в своем коде, вы сможете эффективно решать аналогичные задачи, связанные с поиском K ближайших чисел в отсортированном массиве.