Сортировка вектора по частоте и положению элементов в Rust

Question

У меня есть вектор, и я хочу отсортировать его, где первым критерием является частота. Вторым критерием является положение в векторе. Если два элемента имеют одинаковое количество вхождений, я хочу, чтобы использовался последний элемент, и сначала go. В конце я хочу удалить из него дублирующиеся элементы.

Например, если входные данные:

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

Простой метод состоит в том, чтобы построить га sh карты для частот и положений элементов:

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]

( детская площадка )