Ən yaxın K elementini tapmaq

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon
Geyim AxtarışBaxılıb 34

In Ən yaxın K elementini tapmaq problemi sıraladıq array və x dəyəri. Məsələ, verilmiş massivdə x-a ən yaxın elementlərin K sayını tapmaqdır.

Bir sıra verilmişdir [] = {12, 16, 22, 30, 35, 39, 42,45, 48, 50, 53, 55, 56} və x = 35. Tapşırığınız k = 4-ə ən yaxın elementi tapmaqdır x-ə.

Nəticə: 30,39,42,45

Qeyd edək ki, x massivdədirsə, çıxışda atlanacaq.

Alqoritm

  1. İkili axtarış metodunu elan edin və müəyyənləşdirin.
  2. Bəyan edin a funksiyası həll massiv [], x və k əsas funksiyadan arqument kimi ötürülür.
  3. Mövqeyini qaytaran həll funksiyasından ikili axtarış funksiyasına zəng edin x ilə cp həll funksiyasında.
  4. Set n massiv uzunluğuna, sola cp-1, sağa cp + 1və 0-a qədər sayın.
  5. İçində təkrarlanır döngə zamanı, aşağıdakı şərtədək sıra üzərində, təmin edir:
    1. sol> = 0 və
    2. sağ <n və
    3. say <k
  6. Blok daxil olduqda açın döngə zamanı, şərtlər aşağıdakı kimi verilir:
    1. x - sıra [solda]
    2. massiv [sağ] - x
  7. Şərti yerinə yetirirsə, çap edin sıra [solda] və bunu sol -.
  8. Yuxarıdakı şərt alınmadısa, çap edin massiv [sağ] və bunu sağ ++ və bunu saymaq ++ loopun içərisində.
  9. Sanki kimi verilən şərtlərlə bloku açın (sağ = = n), açın döngə zamanı kimi şərtlərlə verilir say <ksol> = 0 razı olarsa, çap et sıra [solda] və bunu saymaq ++.
  10. Yenə saniyə kimi verilən şərtlərlə blok ikinci açın (solda <0), açın döngə zamanı kimi şərtlərlə verilir say <ksol> = 0, razı olarsa, yazdır massiv [sağ] və bunu saymaq ++.

Arxasındakı yanaşma, əvvəlcə ən yaxın göstəricini tapmaq üçün ikili axtarış edəcəyik x. Sonra K yaxın elementi üçün sola və sağa axtarış aparacağıq.

K-yə ən yaxın elementi tapmaq üçün izah

Beləliklə, sıra içərisindəki x-a ən yaxın 'k' elementlərini tapmaq və vəzifəmizi asanlaşdırmaq üçün ilk işimiz var. Bunun üçün elementin yerini tapmaq üçün ikili axtarış metodundan istifadə edə bilərik, bununla da tapşırıq k ən yaxın elementləri tapmaq asanlaşır.

Beləliklə, əsas fikrimiz x mövqeyini əldə etmək və bəzi əməliyyatlar etmək və verilmiş massivdə x ilə ən az fərqi olan ədədi tapmaqdır. Bunun üçün arr [], x və k arqumentlərini ötürəcəyik. Arr, 0, massivin uzunluğu və mövqeyi tapmaq məcburiyyətində olduğumuz arqumentlər mövqeyin dəyərini aldığımız ikili axtarış funksiyasına ötürülür. Bu mövqe ilə solun x-dən bir az əvvəl və sağın dəyərini x-dan bir qədər sonra təyin edəcəyik, yəni solda = cp -1 (x-dan əvvəl) və sağda cp + 1 (bir az sonra) x).

İndi arr [sol], x-dan bir qədər əvvəlki rəqəmi (x - arr [sol]) (arr [right] –x) -dən az olduqda deməkdir, x-dan dərhal sonra olan rəqəm deməkdir [arr] sol] və sola dönün - növbəti dəfə başqa bir şəkildə arr [sağ] yazdırın və od sayma dəyərini 1 artırmağa davam edin.

misal

Dizinin verildiyini düşünək:

arr = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56};

x = 35, mövqeyi 4-dən 35-ü kimi əldə etdik.

Burada sol = cp -1 = 3 və sağ = cp + 1 = 5

Bu səbəbdən şərti yerinə yetirməyən x - arr [sol] <arr [sağ] - x => 5 <4 müqayisə edirik,

Yəni else blokunda 39 olan arr [right] yazdıracaq və right ++ edin və count = 1 olan count ++.

İndi sol = 3 və sağ 6 olur

Buna görə x - arr [sol] <arr [sağ] - x => 5 <7 müqayisə edirik, bu həqiqi şərtdir,

Beləliklə, blokda 30 olan arr [sol] yazdırılır və sola qoyulur və count = 2 olan ++ sayılır.

Ən yaxın K elementini tapmaqPin

İndi sol = 2 və sağ = 6

Buna görə x - arr [sol] <arr [sağ] - x => 13 <7 müqayisə edirik, bu həqiqi şərtdir,

Yəni else blokunda 42 olan arr [right] yazdıracaq və right ++ edin və count = 3 olan count ++.

İndi sol = 2 və sağ = 7

Beləliklə x - arr [sol] <arr [sağ] - x => 13 <7 müqayisə edirik, bu şərt yerinə yetirilmir,

Beləliklə, başqa bir halda 42 olan arr [right] yazdıracaq və right ++ edin və count = 4 olan count ++.

Ən yaxın K elementini tapmaqPin

İndi sayma vəziyyətimiz uğursuz oldu, demək ki, ən yaxın elementlərimiz var.

Cavabımız da [39 30 42 45].

Həyata keçirilməsi

Ən yaxın elementi tapmaq üçün C ++ proqramı

#include<stdio.h>
int Binary_Search(int arr[], int low, int high, int x)
{
    int mid = (low + high)/2;

    if (arr[high] <= x)
        return high;

    if (arr[low] > x)
        return low;

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

    if(arr[mid] < x)
        return Binary_Search(arr, mid+1, high, x);

    return Binary_Search(arr, low, mid - 1, x);
}

void solution(int arr[], int x, int k, int num)
{
    int y = Binary_Search(arr, 0, num-1, x);
    int r = y+1;
    int count = 0;

    if (arr[y] == x) y--;
    while (y >= 0 && r < num && count < k)
    {
        if (x - arr[y] < arr[r] - x)
            printf("%d ", arr[y--]);
        else
            printf("%d ", arr[r++]);
        count++;
    }

    while (count < k && y >= 0)
        printf("%d ", arr[y--]), count++;

    while (count < k && r < num)
        printf("%d ", arr[r++]), count++;
}

int main()
{
    int arr[] = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56};
    int num = sizeof(arr)/sizeof(arr[0]);
    int x = 35;
    int k = 4;
    solution(arr, x, k, num);
    return 0;
}
39 30 42 45

K ən yaxın elementi tapmaq üçün Java proqramı

public class kce {

  public static int binarySearch(int[] arr,int low, int high, int x){
    int mid = 0;
    while(low<=high){
      mid = (high+low)/2;
      if(arr[mid] == x){
        return mid;
      }
      else if(x<arr[mid]){
        high = mid-1;
      }
      else{
        low = mid+1;
      }
    }

    return mid;

  }

  public static void solution(int[] arr,int x, int k){
    int cp = binarySearch(arr, 0, arr.length-1, x);
    int n = arr.length-1;
    int left = cp-1;
    int right = cp+1;
    int count = 0;


    while(left>=0 && right<n && count <k){
      if(x-arr[left]< arr[right] -x){
        System.out.print(arr[left--] + " ");
        left--;
      }
      else{
        System.out.print(arr[right++] + " ");
        right++;
      }
      count++;

    }

    if(right == n){
      while(count<k && left>=0){
        System.out.print(arr[left] + " ");
        count++;
      }
    }

    if(left < 0){
      while(count<k && left>=0){
        System.out.print(arr[right] + " ");
        count++;
      }
    }


  }

  public static void main(String[]args){

    int k = 4;
    int x = 35;
    int arr1[] = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56};
    solution(arr1,x,k);
  }

}
39 30 45 50

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (Logn + K) hara "N" massivin ölçüsüdür və "K" tapmalı olduğumuz ən yaxın elementin nömrəsidir.

Kosmik Mürəkkəblik

Tamam) lazım olan ən yaxın elementlərin sayını saxlamaq.

References

Translate »