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

链接：658.找到K个最接近的元素
难度：Medium
标签：数组、双指针、二分查找、排序、滑动窗口、堆（优先队列）
简介：给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

题解 1 - rust

• 编辑时间：2022-08-25
• 执行用时：16ms
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：只要数的数量相同就可以匹配。

use std::cmp::Ordering;
use std::collections::{BinaryHeap, VecDeque};
#[derive(PartialEq, Eq, Debug)]
struct Item(i32, i32);
impl PartialOrd for Item {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        let ord = other.1.cmp(&self.1);
        if ord == Ordering::Equal {
            Some(other.0.cmp(&self.0))
        } else {
            Some(ord)
        }
    }
}
impl Ord for Item {
    fn cmp(&self, other: &Self) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}
impl Solution {
    pub fn find_closest_elements(arr: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
        let mut ans = VecDeque::<i32>::new();
        let mut heap = BinaryHeap::<Item>::new();
        for num in arr {
            heap.push(Item(num, (num - x).abs()));
        }
        for _ in 0..k {
            let num = heap.pop().unwrap().0;
            if ans.len() == 0 || *ans.back().unwrap() <= num {
                ans.push_back(num);
            } else {
                ans.push_front(num);
            }
        }
        Vec::from(ans)
    }
}