median and mode

background

The final section of the eighth chapter of the rust book ends with some suggested exercises. The first of which is to write a program that:

Given a list of integers, use a vector and return the median (when sorted, the value in the middle position) and mode (the value that occurs most often; a hash map will be helpful here) of the list.

solution

While straightforward on paper, calculating the median posed a bit of challenge with even lists of numbers. The problem being, when there’s no clear “middle” value the tendency is to take the mean of the 2 middle values. But, Rust being strongly typed, this meant potentially returning a float (i.e. f32) in a function that would otherwise return an integer (i.e. i32).

At this stage in the book, the simple fix just seemd to perform integer division when calculating the mean of even lists.

The mode was simpler. We just needed to keep track of value of the most frequent integer and its frequency. (Looking back, there’s problem a HashMap method for retrieving the value of the minimum/maximum key. Or some equivalent standard library data structure, e.g. priority queue).

use std::collections::HashMap;

fn main() {
    let mut test = vec![3,3,3,5,12,15,15,23,89,500];
    println!("Median: {}\nMode: {}", median(&mut test), mode(&test));
}

fn median(numbers: &mut Vec<i32>) -> i32 {
    numbers.sort();
    let size = numbers.len();
    let i = size / 2;
    if size % 2 == 0 {
        return (numbers[i-1] + numbers[i]) / 2; // integer division so rounding
    }
    return numbers[i];
}

fn mode(numbers: &Vec<i32>) -> i32 {
    let mut freqs = HashMap::<i32, i32>::new();
    let mut max_freq = -1;
    let mut max_freq_int = -1;
    for n in numbers {
        let count = freqs.entry(*n).or_default();
        *count += 1;
        if *count > max_freq {
            max_freq = *count;
            max_freq_int = *n;
        }
    }
    return max_freq_int
}

Median: 13
Mode: 3