根据 Rust 中元素的频率和位置对向量进行排序

Question

我有一个向量，我想对其进行排序，其中第一个标准是频率。第二个标准是向量中的位置。如果两个元素出现的次数相同，我希望最近看到的元素能够利用并先行。最后，我想从中删除重复的元素。

例如，如果输入是这样的：

fn main() {
    let history = vec![3, 2, 4, 6, 2, 4, 3, 3, 4, 5, 6, 3, 2, 4, 5, 5, 3];
}

输出应该是：

3 4 5 2 6

我怎样才能在 Rust 中做到这一点？

Answer 1

一种简单的方法是为元素的频率和位置构建哈希映射：

use std::collections::HashMap;

fn frequency_map(nums: &[i32]) -> HashMap<i32, usize> {
    let mut map = HashMap::new();

    for &n in nums {
        *map.entry(n).or_insert(0) += 1;
    }
    map
}

fn position_map(nums: &[i32]) -> HashMap<i32, usize> {
    let mut map = HashMap::new();

    for (pos, &n) in nums.iter().enumerate() {
        map.insert(n, pos);
    }
    map
}

然后按位置进行不稳定排序，然后按频率进行稳定排序：

fn custom_sort(nums: &mut Vec<i32>) {
    let freq_map = frequency_map(nums);
    let pos_map = position_map(nums);

    nums.sort_unstable_by(|a, b| pos_map.get(b).unwrap().cmp(pos_map.get(a).unwrap()));
    nums.dedup();

    nums.sort_by(|a, b| freq_map.get(b).unwrap().cmp(freq_map.get(a).unwrap()));
}

例子：

use itertools::Itertools;

fn main() {
    let mut history = vec![3, 2, 4, 6, 2, 4, 3, 3, 4, 5, 6, 3, 2, 4, 5, 5, 3];
    custom_sort(&mut history);

    println!("[{}]", history.iter().format(", "));
}

输出：

[3, 4, 5, 2, 6]

（游乐场）