# Leetcode 658. Find K closest elements

2022-04-29 07:21:57

## 658、 find K The closest element

1） Title Description

Given a Sort it out Array of arr , Two integers k and x , Find the closest from the array to x（ The difference between the two numbers is the smallest ） Of k Number . The returned results must be in ascending order .

Integers a Ratio integer b Closer to the x Need to meet ：

• |a - x| < |b - x| perhaps
• |a - x| == |b - x| And a < b

Example 1：

 Input ：arr = [1,2,3,4,5], k = 4, x = 3
Output ：[1,2,3,4]


Example 2：

 Input ：arr = [1,2,3,4,5], k = 4, x = -1
Output ：[1,2,3,4]


Tips ：

• 1 <= k <= arr.length
• 1 <= arr.length <= 10^4
• arr Press Ascending array
• -10^4 <= arr[i], x <= 10^4

2） analysis

Double pointer .

• Required K The number must be continuous in the array ;
• Look from the digits of the array to the middle , Until there is only... Between the two pointers K Elements ;
• Conditions for comparison x − a r r [ l e f t ] > a r r [ r i g h t ] − x x-arr[left]>arr[right]-x when , Move the left pointer one step to the right , Otherwise, the right pointer moves one step to the left .

3）C++ Code

class Solution {

public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {

int left=0;
int right=arr.size()-1;
vector<int> res;
while(right-left>=k){

if(x-arr[left]>arr[right]-x)
left++;
else
right--;
}
while(left<=right)
res.push_back(arr[left++]);
return res;
}
};


copyright notice
author[Die in a trap],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2022/119/202204290424559674.html