如何在未排序的数组或其段中找到第k小的元素？

Question

Rust是否有一个函数可以在数组或数组的一部分中找到第k小的元素？

(类似于C++中的std::nth_element)

- MWB

Answer 1

是的（自 rust 1.49 起）

select_nth_unstable

- georeth

Answer 2

我认为在std中没有这样的函数。

不过，你可以使用crate order_stat，它提供了kth函数。

- Veedrac

Answer 3

希望这能有所帮助。

fn find_smallest_int(arr: &[i32]) -> i32 {
    let mut small_number=arr.to_vec();
    small_number.sort();
    small_number[0]
}

- buraktitiz

---

这个算法的渐进复杂度不正确。 - MWB

嗯，不算错，只是效率低下。 - Makogan