Find K Closest Elements

Description

Given a sorted array arr, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

 

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]

 

Constraints:

• 1 <= k <= arr.length
• 1 <= arr.length <= 10^4
• Absolute value of elements in the array and x will not exceed 10⁴

Solution(javascript)

/*
 * @lc app=leetcode id=658 lang=javascript
 *
 * [658] Find K Closest Elements
 */

// @lc code=start
// /** Binary Search O(log(n) + k)
//  * @param {number[]} arr
//  * @param {number} k
//  * @param {number} x
//  * @return {number[]}
//  */
// const findClosestElements = function (arr, k, x) {
//   let left = 0
//   let right = arr.length - 1
//   let index = left
//   while (left <= right) {
//     const middle = Math.floor(left + (right - left) / 2)
//     if (arr[middle] === x) {
//       index = middle
//       break
//     } else if (arr[middle] < x) {
//       if (x - arr[middle] <= Math.abs(x - arr[index])) {
//         index = middle
//       }
//       left = middle + 1
//     } else {
//       if (arr[middle] - x < Math.abs(x - arr[index])) {
//         index = middle
//       }
//       right = middle - 1
//     }
//   }

//   if (k === 1) {
//     return [arr[index]]
//   }
//   left = index - 1
//   right = index + 1
//   while (right - left - 1 < k) {
//     if (left < 0) {
//       right++
//     } else if (right > arr.length - 1) {
//       left--
//     } else if (x - arr[left] <= arr[right] - x) {
//       left--
//     } else {
//       right++
//     }
//   }
//   return arr.slice(left + 1, right)
// }
/** use sort
 * @param {number[]} arr
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
const findClosestElements = function (arr, k, x) {
  return arr.sort((a, b) => {
    const distanceA = Math.abs(a - x)
    const distanceB = Math.abs(b - x)
    if (distanceA === distanceB) {
      return a - b
    }
    return distanceA - distanceB
  }).slice(0, k)
    .sort((a, b) => a - b)
}
// @lc code=end