README.md

658. Find K Closest Elements

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

• |a - x| < |b - x|, or
• |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]

Constraints:

• 1 <= k <= arr.length
• 1 <= arr.length <= 104
• arr is sorted in ascending order.
• -104 <= arr[i], x <= 104

Solutions (Rust)

1. Binary Search and Two Pointers

impl Solution {
    pub fn find_closest_elements(arr: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
        let mut l = match arr.binary_search(&x) {
            Err(i) if i == arr.len() => return arr.split_at(i - k as usize).1.to_vec(),
            Err(i) if i == 0 => return arr[0..k as usize].to_vec(),
            Err(i) if (arr[i - 1] - x).abs() <= arr[i] - x => i - 1,
            Ok(i) | Err(i) => i,
        };
        let mut r = l + 1;

        while ((r - l) as i32) < k {
            if r == arr.len() || (l > 0 && (arr[l - 1] - x).abs() <= arr[r] - x) {
                l -= 1;
            } else {
                r += 1;
            }
        }

        arr[l..r].to_vec()
    }
}

2. Sort

impl Solution {
    pub fn find_closest_elements(mut arr: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
        arr.sort_unstable_by_key(|&y| ((y - x).abs(), y));
        arr.truncate(k as usize);
        arr.sort_unstable();

        arr
    }
}