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

Rust Solution

struct Solution;

impl Solution {
    fn find_closest_elements(arr: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
        let n = arr.len();
        let k = k as usize;
        let mut l = 0;
        let mut r = n - k;
        while l < r {
            let m = l + (r - l) / 2;
            if x - arr[m] > arr[m + k] - x {
                l = m + 1;
            } else {
                r = m;
            }
        }
        arr[l..l + k].to_vec()
    }
}

#[test]
fn test() {
    let arr = vec![1, 2, 3, 4, 5];
    let k = 4;
    let x = 3;
    let res = vec![1, 2, 3, 4];
    assert_eq!(Solution::find_closest_elements(arr, k, x), res);
    let arr = vec![1, 2, 3, 4, 5];
    let k = 4;
    let x = -1;
    let res = vec![1, 2, 3, 4];
    assert_eq!(Solution::find_closest_elements(arr, k, x), res);
    let arr = vec![1, 1, 1, 10, 10, 10];
    let k = 1;
    let x = 9;
    let res = vec![10];
    assert_eq!(Solution::find_closest_elements(arr, k, x), res);
}

Having problems with this solution? Click here to submit an issue on github.