在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语言中实现这个功能？

- adder

---

只是为了明确算法：您希望将 [1, 2, 3, 4, 5] 排序为 [5, 4, 3, 2, 1]，对吗？ - trent

如果没有重复项，是的。请参见编辑。 - adder

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]

(演示平台)

- L. F.