[Luffy]_658. Find K closest elements

“This is my 33rd day of participating in the First Challenge 2022. For details: First Challenge 2022”

Find K closest elements

The title

Given a sorted array arrarrarr, two integers KKK and XXX, find the number of KKKS closest to XXX (the smallest difference between the two numbers) from the array. The returned results must be sorted in ascending order.

The integer AAA is closer to XXX than the integer BBB.

• ∣ – x ∣ < ∣ b – x ∣ < | | | a – x – x | b ∣ a – x ∣ < ∣ – x ∣ or b
• ∣ a – x ∣ = = b ∣ – x ∣ | a – x – x | | = = | b ∣ a – x ∣ = = ∣ b – x ∣ and a < < ba ba < b

Example 1

Input: arr = [1,2,3,4,5], k = 4, x = 3Copy the code

Example 2

Input: arr = [1, 2, 3, 4, 5], k = 4, x = 1 output: [1, 2, 3, 4]Copy the code

prompt

• 
  $1 <= k <= arr.length$
• 
  $1 <= arr.length <= 10^4$
• Arrarrarr is arranged in ascending order
• 
  $10^4 <= arr[i], x <= 10^4$

Answer key

Double pointer

Find KKK target elements from left and right ends to the middle of the array;

• Leftleftleft represents the left pointer to the array
• Rightrightright indicates the left pointer of the array
• If math. abs(arr[left]−x)<= math. abs(ARr [right]−x) math. abs(arr[left] -x)<= math. abs(arr[right] – X) Math. Abs (arr) [left] – x < = Math. Abs (arr [right] – x); The right pointer moves one step to the left
• Otherwise, the left pointer moves one step to the right.

[left,right][left,right] [left,right

var findClosestElements = function (arr, k, x) {
  const len = arr.length
  if (len === 1) return arr
  if (k === len) return arr
  let left = 0
  let right = len - 1
  while (right - left >= k) {
    const l = arr[left]
    const r = arr[right]
    if (Math.abs(l - x) <= Math.abs(r - x)) {
      right--
    } else {
      left++
    }
  }

  return arr.slice(left, right + 1)}Copy the code

dichotomy

Double Pointers are a bit slow, is there a faster way? binary

Analyzing the ordered array minus the absolute value of the fixed value x, the new array sort can be reduced to the following two possibilities;

This translates to finding k small elements in the array, with the left element taking precedence

The core is X − ARR [mid]> ARR [mid+ K]− XX-ARr [mid]> ARr [mid+ K] -XX − ARr [mid]> ARr [mid+ K]− X

• If x−arr[mid]>arr[mid+k]− xx-arr [mid]>arr[mid+k] -xx −arr[mid +k] >arr[mid+k]−x the smallest k falls on [mid+1,right] [mid + 1, right] [mid + 1, right]
• Otherwise, the smallest KKK number falls in the [left,mid][left,mid] [left,mid] interval
• [left,left+k][left,left+k][left,left+k]

Edit the code as follows

var findClosestElements = function (arr, k, x) {
  const len = arr.length
  let left = 0
  let right = len - k
  while (left < right) {
    const mid = left + ((right - left) >> 1)
    if (x - arr[mid] > arr[mid + k] - x) {
      left = mid + 1
    } else {
      right = mid
    }
  }

  return arr.slice(left, left + k)
}
Copy the code

conclusion

The author level is limited, if there is insufficient welcome to correct; Any comments and suggestions are welcome in the comments section