Рубрики

Найти k ближайших элементов к заданному значению

Учитывая отсортированный массив arr [] и значение X, найдите k ближайших к X элементов в arr [].
Примеры:

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

Обратите внимание, что если элемент присутствует в массиве, то он не должен быть в выводе, требуются только другие ближайшие элементы.

В следующих решениях предполагается, что все элементы массива различны.

Простым решением является линейный поиск k ближайших элементов.
1) Начните с первого элемента и найдите точку пересечения (точка, до которой элементы меньше или равны X и после которых элементы больше). Этот шаг занимает O (N) времени.
2) Как только мы находим точку пересечения, мы можем сравнить элементы по обе стороны от точки пересечения, чтобы вывести k ближайших элементов. Этот шаг занимает O (K) времени.

Временная сложность вышеуказанного решения составляет O (n).

Оптимизированное решение — найти k элементов за O (Logn + k) времени. Идея состоит в том, чтобы использовать двоичный поиск, чтобы найти точку пересечения. Как только мы находим индекс точки пересечения, мы можем вывести k ближайших элементов за O (k) время.

C / 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;  / * низкий + (высокий - низкий) / 2 * /

  

  / * Если x совпадает со средним элементом, вернуть mid * /

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

    return mid;

  

  / * Если x больше, чем arr [mid], то либо arr [mid + 1]

    потолок x или потолок в arr [mid + 1 ... high] * /

  if(arr[mid] < x)

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

  

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

}

  
// Эта функция печатает k ближайших элементов к x в arr [].
// n - количество элементов в arr []

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; // Отслеживать количество уже напечатанных элементов

  

    // Если x присутствует в arr [], то уменьшаем левый индекс

    // Предположение: все элементы в arr [] различны

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

  

    // Сравнить элементы слева и справа от кроссовера

    // указать, чтобы найти k ближайших элементов

    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-программа для поиска k ближайших элементов к заданному значению

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/ * низкий + (высокий - низкий) / 2 * /

  

        / * Если x совпадает со средним элементом, вернуть mid * /

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

            return mid;

  

        / * Если x больше, чем arr [mid], то либо arr [mid + 1]

          потолок x или потолок в arr [mid + 1 ... high] * /

        if(arr[mid] < x)

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

  

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

    }

  

    // Эта функция печатает k ближайших элементов к x в arr [].

    // n - количество элементов в arr []

    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; // Отслеживать количество элементов

                       // уже напечатано

  

        // Если x присутствует в arr [], то уменьшаем левый индекс

        // Предположение: все элементы в arr [] различны

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

  

        // Сравнить элементы слева и справа от кроссовера

        // указать, чтобы найти k ближайших элементов

        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

# Функция, чтобы найти точку пересечения
# (точка, перед которой элементы
# меньше или равно x и после
# которое больше х)

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

  

    # Базовые случаи

    if (arr[high] <= x) : # х больше всех

        return high

          

    if (arr[low] > x) : # х меньше всех

        return low 

      

    # Найти среднюю точку

    mid = (low + high) // 2 # низкий + (высокий - низкий) // 2

      

    # Если х совпадает со средним элементом,

    # затем вернитесь в середине

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

        return mid 

      

    # Если x больше, чем arr [mid], то

    # либо обр [середина + 1] является потолком х

    # или потолок лежит в обр [средняя + 1 ... высокая]

    if(arr[mid] < x) :

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

      

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

  
# Эта функция выводит k ближайших элементов в x
# в обр []. n - количество элементов в arr []

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

      

    # Найти точку пересечения

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

    r = l + 1 # Правильный индекс для поиска

    count = 0 # Чтобы отслеживать количество

              # элементы уже напечатаны

  

    # Если x присутствует в arr [], то уменьшить

    # левый индекс. Предположение: все элементы

    # в arr [] различны

    if (arr[l] == x) :

        l -= 1

  

    # Сравнить элементы слева и справа от кроссовера

    # указать, чтобы найти k ближайших элементов

    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

  

    # Если справа нет больше элементов

    # side, затем печатать левые элементы

    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)

      
# Этот код предоставлен Ryuga

C #

// C # программа для поиска k ближайших элементов к
// данное значение

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;

  

        // Найти среднюю точку

        / * низкий + (высокий - низкий) / 2 * /

        int mid = (low + high)/2; 

  

        / * Если х совпадает со средним элементом, то

        вернуться в середине * /

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

            return mid;

  

        / * Если x больше, чем arr [mid], то

        либо arr [mid + 1] является потолком x, либо

        потолок лежит в обр [средняя + 1 ... высокая] * /

        if(arr[mid] < x)

            return findCrossOver(arr, mid+1, 

                                      high, x);

  

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

    }

  

    // Эта функция печатает k ближайших элементов

    // к х в обр []. n это число

    // элементы в arr []

    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; 

  

        // Если x присутствует в arr [], тогда уменьшаем

        // левый индекс Предположение: все элементы в

        // arr [] различны

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

  

        // Сравнить элементы слева и справа от

        // точка пересечения, чтобы найти k ближайших

        // элементы

        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
// PHP программа для поиска k ближайших
// элементы с заданным значением

  
/ * Функция найти крест

   над точкой (точка перед

   какие элементы меньше

   чем или равно х и после

   который больше чем х) * /

function findCrossOver($arr, $low

                       $high, $x)

{

      

    // Базовые случаи

      

    // х больше всех

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

        return $high;

          

    // х меньше всех

    if ($arr[$low] > $x

        return $low;

      

    // Найти среднюю точку

    / * низкий + (высокий - низкий) / 2 * /

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

      

    / * Если х совпадает со средним

       элемент, затем верните середину * /

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

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

        return $mid;

      

    / * Если x больше, чем arr [mid],

       тогда либо arr [mid + 1]

       потолок х или потолок лежит

       в обр [средняя + 1 ... высокая] * /

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

        return findCrossOver($arr, $mid + 1, 

                                 $high, $x);

      

    return findCrossOver($arr, $low,

                      $mid - 1, $x);

}

  
// Эта функция печатает k
// ближайшие элементы к x в arr [].
// n - количество элементов
// в обр []

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

{

      

    // Найти точку пересечения

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

      

    // Правильный индекс для поиска

    $r = $l + 1;

      

    // Для отслеживания количества

    // элементы уже напечатаны

    $count = 0; 

  

    // Если x присутствует в arr [],

    // затем уменьшаем левый индекс

    // Предположение: все элементы

    // в arr [] различны

    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);

  
// Этот код предоставлен anuj_67.
?>


Выход:

39 30 42 45

Временная сложность этого метода составляет O (Logn + k).

Упражнение: Расширение оптимизированного решения для работы и для дубликатов, т. Е. Для работы с массивами, где элементы не должны быть различимыми.

Эта статья пополняемая Рахул Джейна. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Найти k ближайших элементов к заданному значению

0.00 (0%) 0 votes