1854. 人口最多的年份 Maximum Population Year

问题描述

这是一个计数的问题, 首先想到的就是字典计数.

BTreeMap

计数步骤如下:

1. 创建字典, 为了找到相同生存人数的最小年份, 我们使用 BTreeMap 来保证年份的有序.
2. 遍历 logs 中的所有记录, 并遍历每条记录的出生到去世间的所有年份, 将本年度加入到字典中
3. 遍历有序字典, 找到有最大生存人数的那一年

#![allow(unused)]
fn main() {
use std::collections::BTreeMap;

// Hashmap
// 使用字典计数
pub fn maximum_population1(logs: Vec<Vec<i32>>) -> i32 {
    debug_assert!(!logs.is_empty());
    // 因为要得到最早的年份, 我们使用 BTreeMap 来保证年份有序.
    let mut map = BTreeMap::new();

    for log in logs {
        for year in log[0]..log[1] {
            *map.entry(year).or_default() += 1;
        }
    }

    let mut max_count = 0;
    let mut max_year = 0;
    for (year, count) in map {
        if count > max_count {
            max_count = count;
            max_year = year;
        }
    }
    max_year
}
}

这个算法的时间复杂度是 O(n * m), 其中 n 是人数, m 是生存的年份. 空间复杂度是 O(n), 其中 n 是 logs 的年份范围.

计数数组

因为年份跨度比较小, 只有100年, 我们可以用栈上的数组来代替 BTreeMap, 其它步骤没有太多变化.

#![allow(unused)]
fn main() {
// 计数
// 使用数组代替字典
pub fn maximum_population2(logs: Vec<Vec<i32>>) -> i32 {
    const MAX_YEARS: usize = 100;
    debug_assert!(!logs.is_empty());
    let start_year: usize = 1950;
    let mut timeline = [0; MAX_YEARS];

    for log in logs {
        for year in log[0]..log[1] {
            timeline[year as usize - start_year] += 1;
        }
    }

    let mut max_count = 0;
    let mut max_year = 0;
    for (year, &count) in timeline.iter().enumerate() {
        if count > max_count {
            max_count = count;
            max_year = year;
        }
    }
    (max_year + start_year) as i32
}
}

这个算法的时间复杂度是 O(n * m), 其中 n 是人数, m 是生存的年份. 空间复杂度是 O(n), 其中 n 是 logs 的年份范围.

前缀和

这个有些不好考虑, 在构造前缀和数组之前, 我们先构造一个辅助数组. 整个解决步骤如下:

1. 创建 alive 辅助数组
2. 遍历 logs 数组
   1. 当一个人出生时, 将 alive 中出生所在年份计数加1, alive[start_year] += 1
   2. 当一个人去世时, 将 alive 中去世所在年份计数减1, alive[end_year] -= 1
3. 创建 prefix_sum 前缀和数组, 通过遍历 alive 数组
4. 最后遍历 prefix_sum 数组, 找到生存人数最多的那个年份

#![allow(unused)]
fn main() {
// Prefix Sum
pub fn maximum_population3(logs: Vec<Vec<i32>>) -> i32 {
    let start_year = 1950;
    let end_year = 2050;
    let no_years = end_year - start_year + 1;

    // 构造数组, 用于记录每年增减的人数,
    // 为构造前缀和数组做准备
    let mut alive = vec![0; no_years as usize];
    for log in logs {
        let start_year_index = (log[0] - start_year) as usize;
        let end_year_index = (log[1] - start_year) as usize;
        alive[start_year_index] += 1;
        alive[end_year_index] -= 1;
    }

    // 构造前缀和数组
    let mut prefix_sum = vec![0; alive.len()];
    prefix_sum[0] = alive[0];
    for i in 1..alive.len() {
        prefix_sum[i] = prefix_sum[i - 1] + alive[i];
    }

    // 遍历前缀和数组, 找到最多的人所在的年份
    let mut max_count = 0;
    let mut max_year = 0;
    for (index, count) in prefix_sum.into_iter().enumerate() {
        if count > max_count {
            max_count = count;
            max_year = index as i32 + start_year;
        }
    }
    max_year
}
}

这个算法的时间复杂度是 O(n), 空间复杂度是 O(n), 其中 n 是 logs 的年份范围.