假设我们有一个排序数组,还给出了两个整数k和x,我们必须在该数组中找到k个最接近x的元素。结果应按升序排序。如果有平局,总是首选较小的元素。因此,如果输入像[1,2,3,4,5]并且k = 4,x = 3,那么输出将是[1,2,3,4]
为了解决这个问题,我们将遵循以下步骤-
创建一个称为ans的数组
设置低:= 0,高:=数组大小– k
从低到高
中:=低+(高-低)/ 2
如果x – arr [mid]> arr [mid + k] – x,则低:=中+ 1,否则高:=中
对于从低到低+ k的范围
将arr [i]插入ans数组
返回ans
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: vector<int> findClosestElements(vector<int>& arr, int k, int x) { vector <int> ans; int low = 0; int high = arr.size() - k; while(low < high){ int mid = low + (high - low)/2; if(x - arr[mid] > arr[mid + k] - x){ low = mid + 1; } else high = mid; } for(int i = low ; i < low + k ; i++)ans.push_back(arr[i]); return ans; } }; main(){ Solution ob; vector<int> v = {1,2,3,4,5}; print_vector(ob.findClosestElements(v, 4, 3)); }
[1,2,3,4,5] 4 3
输出结果
[1,2,3,4]