برنامه پیدا کردن k نزدیک ترین عنصر به یک مقدار — راهنمای کاربردی
در این مطلب، روش نوشتن برنامه پیدا کردن k نزدیک ترین عنصر به یک مقدار خاص داده شده در ورودی، آموزش داده شده است. یک آرایه مرتب شده arr[] و مقدار X موجود است. هدف پیدا کردن k عنصر نزدیک به مقدار X در آرایه arr[] است. مثالهای زیر در این رابطه قابل توجه هستند. شایان ذکر است، پیادهسازی روش آموزش داده شده در این مطلب، در زبانهای برنامهنویسی گوناگون شامل «سیپلاسپلاس» (++C)، «سی» (C)، «جاوا» (Java)، «پایتون ۳» (Python 3) و «پیاچپی» (PHP) انجام شده است.
Input: K = 4, X = 35 arr[] = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56} Output: 30 39 42 45
شایان توجه است که اگر خود عنصر X در آرایه وجود داشته باشد، نباید در خروجی ارائه شود. در واقع، تنها نزدیکترین عناصر به X هستند که باید در خروجی بازگردانده شوند. در راهکارهای زیر، فرض میشود همه عناصر اولیه از یکدیگر متمایز هستند. یک راهکار ساده، انجام جستجوی خطی برای k نزدیکترین عنصر است.
جستجوی خطی برای پیدا کردن k نزدیک ترین عنصر به یک مقدار
- کار را از اولین عنصر آغاز کن و جستجو را برای «نقطه همگذری» (Crossover Point) (نقطهای پیش از X که عناصر کوچکتر یا مساوی X باشند و همچنین، نقطهای پس از X که در آن عناصر بزرگتر از X هستند) انجام بده. این گام از مرتبه O(n) است.
- هنگامی که نقطه همگذری پیدا شد، میتوان عناصر را در دو سمت نقطه همگذری برای چاپ کردن k نزدیکترین عنصر مقایسه کرد. این گام از درجه O(k) است.
جستجوی دودویی برای پیدا کردن k نزدیک ترین عنصر به یک مقدار
پیچیدگی زمانی راهکار بالا (جستجوی خطی) از درجه O(n) است. یک راهکار بهینه، پیدا کردن k عنصر در زمان O(Logn + k) است. برای رسیدن به زمان بیان شده، یک ایده استفاده از «جستجوی دودویی» (Binary Search) برای پیدا کردن نقطه همگذری است. هنگامی که اندیس نقطه همگذری پیدا شد، میتوان k نزدیکترین عنصر را در زمان O(k) پیدا کرد.
پیدا کردن k نزدیک ترین عنصر به یک مقدار در C/C++ با جستجوی دودویی
1#include<stdio.h>
2
3/* Function to find the cross over point (the point before
4 which elements are smaller than or equal to x and after
5 which greater than x)*/
6int findCrossOver(int arr[], int low, int high, int x)
7{
8 // Base cases
9 if (arr[high] <= x) // x is greater than all
10 return high;
11 if (arr[low] > x) // x is smaller than all
12 return low;
13
14 // Find the middle point
15 int mid = (low + high)/2; /* low + (high - low)/2 */
16
17 /* If x is same as middle element, then return mid */
18 if (arr[mid] <= x && arr[mid+1] > x)
19 return mid;
20
21 /* If x is greater than arr[mid], then either arr[mid + 1]
22 is ceiling of x or ceiling lies in arr[mid+1...high] */
23 if(arr[mid] < x)
24 return findCrossOver(arr, mid+1, high, x);
25
26 return findCrossOver(arr, low, mid - 1, x);
27}
28
29// This function prints k closest elements to x in arr[].
30// n is the number of elements in arr[]
31void printKclosest(int arr[], int x, int k, int n)
32{
33 // Find the crossover point
34 int l = findCrossOver(arr, 0, n-1, x);
35 int r = l+1; // Right index to search
36 int count = 0; // To keep track of count of elements already printed
37
38 // If x is present in arr[], then reduce left index
39 // Assumption: all elements in arr[] are distinct
40 if (arr[l] == x) l--;
41
42 // Compare elements on left and right of crossover
43 // point to find the k closest elements
44 while (l >= 0 && r < n && count < k)
45 {
46 if (x - arr[l] < arr[r] - x)
47 printf("%d ", arr[l--]);
48 else
49 printf("%d ", arr[r++]);
50 count++;
51 }
52
53 // If there are no more elements on right side, then
54 // print left elements
55 while (count < k && l >= 0)
56 printf("%d ", arr[l--]), count++;
57
58 // If there are no more elements on left side, then
59 // print right elements
60 while (count < k && r < n)
61 printf("%d ", arr[r++]), count++;
62}
63
64/* Driver program to check above functions */
65int main()
66{
67 int arr[] ={12, 16, 22, 30, 35, 39, 42,
68 45, 48, 50, 53, 55, 56};
69 int n = sizeof(arr)/sizeof(arr[0]);
70 int x = 35, k = 4;
71 printKclosest(arr, x, 4, n);
72 return 0;
73}
پیدا کردن k نزدیک ترین عنصر به یک مقدار در جاوا با جستجوی دودویی
1// Java program to find k closest elements to a given value
2class KClosest
3{
4 /* Function to find the cross over point (the point before
5 which elements are smaller than or equal to x and after
6 which greater than x)*/
7 int findCrossOver(int arr[], int low, int high, int x)
8 {
9 // Base cases
10 if (arr[high] <= x) // x is greater than all
11 return high;
12 if (arr[low] > x) // x is smaller than all
13 return low;
14
15 // Find the middle point
16 int mid = (low + high)/2; /* low + (high - low)/2 */
17
18 /* If x is same as middle element, then return mid */
19 if (arr[mid] <= x && arr[mid+1] > x)
20 return mid;
21
22 /* If x is greater than arr[mid], then either arr[mid + 1]
23 is ceiling of x or ceiling lies in arr[mid+1...high] */
24 if(arr[mid] < x)
25 return findCrossOver(arr, mid+1, high, x);
26
27 return findCrossOver(arr, low, mid - 1, x);
28 }
29
30 // This function prints k closest elements to x in arr[].
31 // n is the number of elements in arr[]
32 void printKclosest(int arr[], int x, int k, int n)
33 {
34 // Find the crossover point
35 int l = findCrossOver(arr, 0, n-1, x);
36 int r = l+1; // Right index to search
37 int count = 0; // To keep track of count of elements
38 // already printed
39
40 // If x is present in arr[], then reduce left index
41 // Assumption: all elements in arr[] are distinct
42 if (arr[l] == x) l--;
43
44 // Compare elements on left and right of crossover
45 // point to find the k closest elements
46 while (l >= 0 && r < n && count < k)
47 {
48 if (x - arr[l] < arr[r] - x)
49 System.out.print(arr[l--]+" ");
50 else
51 System.out.print(arr[r++]+" ");
52 count++;
53 }
54
55 // If there are no more elements on right side, then
56 // print left elements
57 while (count < k && l >= 0)
58 {
59 System.out.print(arr[l--]+" ");
60 count++;
61 }
62
63
64 // If there are no more elements on left side, then
65 // print right elements
66 while (count < k && r < n)
67 {
68 System.out.print(arr[r++]+" ");
69 count++;
70 }
71 }
72
73 /* Driver program to check above functions */
74 public static void main(String args[])
75 {
76 KClosest ob = new KClosest();
77 int arr[] = {12, 16, 22, 30, 35, 39, 42,
78 45, 48, 50, 53, 55, 56
79 };
80 int n = arr.length;
81 int x = 35, k = 4;
82 ob.printKclosest(arr, x, 4, n);
83 }
84}
85/* This code is contributed by Rajat Mishra */
پیدا کردن k نزدیک ترین عنصر به یک مقدار در پایتون ۳ با جستجوی دودویی
1# Function to find the cross over point
2# (the point before which elements are
3# smaller than or equal to x and after
4# which greater than x)
5def findCrossOver(arr, low, high, x) :
6
7 # Base cases
8 if (arr[high] <= x) : # x is greater than all
9 return high
10
11 if (arr[low] > x) : # x is smaller than all
12 return low
13
14 # Find the middle point
15 mid = (low + high) // 2 # low + (high - low)// 2
16
17 # If x is same as middle element,
18 # then return mid
19 if (arr[mid] <= x and arr[mid + 1] > x) :
20 return mid
21
22 # If x is greater than arr[mid], then
23 # either arr[mid + 1] is ceiling of x
24 # or ceiling lies in arr[mid+1...high]
25 if(arr[mid] < x) :
26 return findCrossOver(arr, mid + 1, high, x)
27
28 return findCrossOver(arr, low, mid - 1, x)
29
30# This function prints k closest elements to x
31# in arr[]. n is the number of elements in arr[]
32def printKclosest(arr, x, k, n) :
33
34 # Find the crossover point
35 l = findCrossOver(arr, 0, n - 1, x)
36 r = l + 1 # Right index to search
37 count = 0 # To keep track of count of
38 # elements already printed
39
40 # If x is present in arr[], then reduce
41 # left index. Assumption: all elements
42 # in arr[] are distinct
43 if (arr[l] == x) :
44 l -= 1
45
46 # Compare elements on left and right of crossover
47 # point to find the k closest elements
48 while (l >= 0 and r < n and count < k) :
49
50 if (x - arr[l] < arr[r] - x) :
51 print(arr[l], end = " ")
52 l -= 1
53 else :
54 print(arr[r], end = " ")
55 r += 1
56 count += 1
57
58 # If there are no more elements on right
59 # side, then print left elements
60 while (count < k and l >= 0) :
61 print(arr[l], end = " ")
62 l -= 1
63 count += 1
64
65 # If there are no more elements on left
66 # side, then print right elements
67 while (count < k and r < n) :
68 print(arr[r], end = " ")
69 r += 1
70 count += 1
71
72# Driver Code
73if __name__ == "__main__" :
74
75 arr =[12, 16, 22, 30, 35, 39, 42,
76 45, 48, 50, 53, 55, 56]
77
78 n = len(arr)
79 x = 35
80 k = 4
81
82 printKclosest(arr, x, 4, n)
83
84# This code is contributed by Ryuga
پیدا کردن k نزدیک ترین عنصر به یک مقدار در C# با جستجوی دودویی
1// C# program to find k closest elements to
2// a given value
3using System;
4
5class GFG {
6
7 /* Function to find the cross over point
8 (the point before which elements are
9 smaller than or equal to x and after which
10 greater than x)*/
11 static int findCrossOver(int []arr, int low,
12 int high, int x)
13 {
14
15 // Base cases
16 // x is greater than all
17 if (arr[high] <= x)
18 return high;
19
20 // x is smaller than all
21 if (arr[low] > x)
22 return low;
23
24 // Find the middle point
25 /* low + (high - low)/2 */
26 int mid = (low + high)/2;
27
28 /* If x is same as middle element, then
29 return mid */
30 if (arr[mid] <= x && arr[mid+1] > x)
31 return mid;
32
33 /* If x is greater than arr[mid], then
34 either arr[mid + 1] is ceiling of x or
35 ceiling lies in arr[mid+1...high] */
36 if(arr[mid] < x)
37 return findCrossOver(arr, mid+1,
38 high, x);
39
40 return findCrossOver(arr, low, mid - 1, x);
41 }
42
43 // This function prints k closest elements
44 // to x in arr[]. n is the number of
45 // elements in arr[]
46 static void printKclosest(int []arr, int x,
47 int k, int n)
48 {
49
50 // Find the crossover point
51 int l = findCrossOver(arr, 0, n-1, x);
52
53 // Right index to search
54 int r = l + 1;
55
56 // To keep track of count of elements
57 int count = 0;
58
59 // If x is present in arr[], then reduce
60 // left index Assumption: all elements in
61 // arr[] are distinct
62 if (arr[l] == x) l--;
63
64 // Compare elements on left and right of
65 // crossover point to find the k closest
66 // elements
67 while (l >= 0 && r < n && count < k)
68 {
69 if (x - arr[l] < arr[r] - x)
70 Console.Write(arr[l--]+" ");
71 else
72 Console.Write(arr[r++]+" ");
73 count++;
74 }
75
76 // If there are no more elements on right
77 // side, then print left elements
78 while (count < k && l >= 0)
79 {
80 Console.Write(arr[l--]+" ");
81 count++;
82 }
83
84 // If there are no more elements on left
85 // side, then print right elements
86 while (count < k && r < n)
87 {
88 Console.Write(arr[r++] + " ");
89 count++;
90 }
91 }
92
93 /* Driver program to check above functions */
94 public static void Main()
95 {
96 int []arr = {12, 16, 22, 30, 35, 39, 42,
97 45, 48, 50, 53, 55, 56};
98 int n = arr.Length;
99 int x = 35;
100 printKclosest(arr, x, 4, n);
101 }
102}
103
104// This code is contributed by nitin mittal.
پیدا کردن k نزدیک ترین عنصر به یک مقدار در PHP با جستجوی دودویی
1<?php
2// PHP Program to Find k closest
3// elements to a given value
4
5/* Function to find the cross
6 over point (the point before
7 which elements are smaller
8 than or equal to x and after
9 which greater than x) */
10function findCrossOver($arr, $low,
11 $high, $x)
12{
13
14 // Base cases
15
16 // x is greater than all
17 if ($arr[$high] <= $x)
18 return $high;
19
20 // x is smaller than all
21 if ($arr[$low] > $x)
22 return $low;
23
24 // Find the middle point
25 /* low + (high - low)/2 */
26 $mid = ($low + $high)/2;
27
28 /* If x is same as middle
29 element, then return mid */
30 if ($arr[$mid] <= $x and
31 $arr[$mid + 1] > $x)
32 return $mid;
33
34 /* If x is greater than arr[mid],
35 then either arr[mid + 1] is
36 ceiling of x or ceiling lies
37 in arr[mid+1...high] */
38 if($arr[$mid] < $x)
39 return findCrossOver($arr, $mid + 1,
40 $high, $x);
41
42 return findCrossOver($arr, $low,
43 $mid - 1, $x);
44}
45
46// This function prints k
47// closest elements to x in arr[].
48// n is the number of elements
49// in arr[]
50function printKclosest($arr, $x, $k, $n)
51{
52
53 // Find the crossover point
54 $l = findCrossOver($arr, 0, $n - 1, $x);
55
56 // Right index to search
57 $r = $l + 1;
58
59 // To keep track of count of
60 // elements already printed
61 $count = 0;
62
63 // If x is present in arr[],
64 // then reduce left index
65 // Assumption: all elements
66 // in arr[] are distinct
67 if ($arr[$l] == $x) $l--;
68
69 // Compare elements on left
70 // and right of crossover
71 // point to find the k
72 // closest elements
73 while ($l >= 0 and $r < $n
74 and $count < $k)
75 {
76 if ($x - $arr[$l] < $arr[$r] - $x)
77 echo $arr[$l--]," ";
78 else
79 echo $arr[$r++]," ";
80 $count++;
81 }
82
83 // If there are no more
84 // elements on right side,
85 // then print left elements
86 while ($count < $k and $l >= 0)
87 echo $arr[$l--]," "; $count++;
88
89 // If there are no more
90 // elements on left side,
91 // then print right elements
92 while ($count < $k and $r < $n)
93 echo $arr[$r++]; $count++;
94}
95
96// Driver Code
97$arr =array(12, 16, 22, 30, 35, 39, 42,
98 45, 48, 50, 53, 55, 56);
99$n = count($arr);
100$x = 35; $k = 4;
101
102printKclosest($arr, $x, 4, $n);
103
104// This code is contributed by anuj_67.
105?>
خروجی قطعه کدهای بالا به صورت زیر است.
39 30 42 45
پیچیدگی زمانی این روش از درجه O(Logn + k) است.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامهنویسی
- آموزش برنامهنویسی C++
- مجموعه آموزشهای ریاضیات
- یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
- الگوریتم بازی مار و پله همراه با کد — به زبان ساده
- حل مساله n وزیر با الگوریتم پسگرد (Backtracking) — به زبان ساده
- الگوریتم جست و جوی دودویی در جاوا اسکریپت — به زبان ساده
^^