current position:Home>Leetcode 658. Find K closest elements

Leetcode 658. Find K closest elements

2022-04-29 07:21:57Die in a trap

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 xarr[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

Random recommended