658. 找到 K 个最接近的元素

658. 找到 K 个最接近的元素

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

---

二分法 + 双指针 先 findFirstIndex ， 如果找不到，返回最后一个下标。 找到后，开始中间向两边走 左右指针中寻找K个最靠近的元素 。 左边无效，右边有效； 右边无效，左边优先。 左右都寻找距离最近的元素。

---

impl Solution {
    pub fn find_closest_elements(arr: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
        let (i, found) = match arr.binary_search(&x) {
            Ok(i) => (i as i32, true),
            Err(i) => (i as i32, false),
        };
 
        let n = arr.len();
        let mut left = if found { i } else { i - 1 } as i32;
        let mut right = left + 1;
 
 
        for _ in 0..k {
            if left < 0 {
                right += 1;
            } else if right as usize >= n || x - arr[left as usize] <= arr[right as usize] - x {
                left -= 1;
            } else {
                right += 1;
            }
        }
 
        arr[(left + 1) as usize..right as usize].to_vec()
    }
}
 
#[cfg(test)]
mod test {
    use super::*;
 
    #[test]
    fn test_it() {
        assert_eq!(vec![1, 2, 2, 2], Solution::find_closest_elements(vec![1, 2, 2, 2, 5, 5, 5, 8, 9, 9], 4, 0));
        assert_eq!(vec![1, 2, 3, 4], Solution::find_closest_elements(vec![1, 2, 3, 4, 5], 4, 3));
    }
}

#算法/二分#算法/双指针