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