在 C++ 中找到最接近指定值 k 个元素
考虑我们有一个包含一些元素的数组 A。我们还有另外两个值 X 和 k。我们的任务是从数组 A 中找到 X 的最接近的 k 个数字。如果元素 X 出现在数组中,它将不会显示在输出中。如果 A = [12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56] 并且 X = 35,k = 4。输出将为 30、39、42、45。
为了解决此问题,我们将采用二分搜索方法。使用此方法,我们将获得交叉点。如果找到交叉点的索引,我们可以在 O(k) 时间内打印最接近的 k 个元素。
示例
#include<iostream> using namespace std; int getCrossoverPoint(int arr[], int left, int right, int x) { if (arr[right] <= x) return right; if (arr[left] > x) return left; int mid = (left + right)/2; if(arr[mid] <= x && arr[mid+1] > x) return mid; if(arr[mid] < x) return getCrossoverPoint(arr, mid+1, right, x); return getCrossoverPoint(arr, left, mid - 1, x); } void findKClosestNumbers(int arr[], int x, int k, int n) { int l = getCrossoverPoint(arr, 0, n-1, x); int r = l+1; int count = 0; if (arr[l] == x) l--; while (l >= 0 && r < n && count < k) { if (x - arr[l] < arr[r] - x) cout << arr[l--] << " "; else cout << arr[r++] << " "; count++; } while (count < k && l >= 0){ cout << arr[l--] << " "; count++; } while (count < k && r < n){ cout << 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 = 5; findKClosestNumbers(arr, x, k, n); }
输出
39 30 42 45 48
广告