Re: [閒聊] 每日leetcode

[yam276 (虛構史學家)]

※ 引述《sustainer123 (caster )》之銘言：
: 1051. Height Checker
: 給定一數列heights 我們期待heights是一非遞減數列
: 看解答好像能把時間複雜度降到n 等等研究一下

思路:

用bucket

然後這題用HashMap沒特別省時間

還會耗空間資源

這種小範圍的還是直接用Vec比較好

但我都寫了

:(


Code:

use std::collections::HashMap;

impl Solution {
    pub fn height_checker(heights: Vec<i32>) -> i32 {
        let mut heights_freq= HashMap::new();
        for &num in &heights {
            *heights_freq.entry(num).or_insert(0) += 1;
        }

        let mut index = 0;
        let mut result = 0;

        for height in 0..=100 {
            if let Some(&count) = heights_freq.get(&(height as i32)) {
                for _ in 0..count {
                    if heights[index] != height as i32 {
                        result +=1;
                    }
                    index += 1;
                }
            }
        }

        result
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.249.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718027883.A.B0D.html
推 DJYOSHITAKA: 別捲了
推 sustainer123: 大佬
→ nh60211as: 大師
推 oin1104: 大師
推 Smallsh: 大師 尼板剩我不會hashmap