برنامه پیدا کردن k نزدیک ترین عنصر به یک مقدار — راهنمای کاربردی

۲۰۰ بازدید
آخرین به‌روزرسانی: ۱۹ تیر ۱۴۰۲
زمان مطالعه: ۹ دقیقه
برنامه پیدا کردن 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 نزدیک ترین عنصر به یک مقدار

  1. کار را از اولین عنصر آغاز کن و جستجو را برای «نقطه هم‌گذری» (Crossover Point) (نقطه‌ای پیش از X که عناصر کوچک‌تر یا مساوی X باشند و همچنین، نقطه‌ای پس از X که در آن عناصر بزرگ‌تر از X هستند) انجام بده. این گام از مرتبه O(n)‎ است.
  2. هنگامی که نقطه هم‌گذری پیدا شد، می‌توان عناصر را در دو سمت نقطه هم‌گذری برای چاپ کردن 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)‎ است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۱ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *