在Day5提交Leetcode1679中發現使用Hashmap慢了許多，因此今天來分析一下時間複雜度。

時間複雜度常用O符號表述，描述該演算法執行時間，使用這種方式時，時間複雜度是漸近的，也就是輸入值大小趨近無窮時的情況。如果一個演算法對於任何大小為 n 的輸入，它至多需要 5n^3 + 3n 的時間執行完畢，那麼它的漸近時間複雜度是 O(n^3)，關於如何估計可以參考neetcode Big O Notation Cheat Sheet。

為什麼只取「最大」的那一項？

主導成長速度:當輸入n很大時，只有「最高次方」的那個項，會決定演算法的效率。

O(n^2 + n) vs O(n^2)，n極大時，主要受n^2影響，因此這兩個都是O(n^2)。

分析1679為何排序比較快

1. 首先我們可以看到測資長度1 <= nums.length <= 10^5

2. Hashmap每個元素進去都要計算一次雜湊值(hash)

3. Hashmap每次查找/插入，會根據 key 做雜湊找到bucket的位置。

4. Hashmap遇到碰撞還需碰撞處理

做了以上這些運算但在估時間複雜度都會是O(1)，跑完整個輸入建立hashMapO(n)，所以在估時省略了常數項。
我們實際寫個code比較，1000筆隨機數字先排序再走完向量加總跟先建好hashmap再依序加總的時間差

use std::time::Instant;
use std::collections::HashMap;
use rand::seq::SliceRandom;
use rand::thread_rng;

fn main() {
    let n = 1000;
    // 產生 0..n 的亂序向量
    let mut v: Vec<usize> = (0..n).collect();
    v.shuffle(&mut thread_rng());

    // 排序後走訪向量
    let mut v_sorted = v.clone();
    v_sorted.sort_unstable();
    let start = Instant::now();
    let sum_vec: usize = v_sorted.iter().sum();
    let duration_vec = start.elapsed();
    println!("Vec sorted sum: {}, time: {:?}", sum_vec, duration_vec);

    // 建立 HashMap
    let mut map = HashMap::with_capacity(n);
    for (i, &val) in v.iter().enumerate() {
        map.insert(i, val);
    }

    // 依序用 key 走訪 HashMap
    let start = Instant::now();
    let mut sum_map = 0;
    for i in 0..n {
        sum_map += *map.get(&i).unwrap();
    }
    let duration_map = start.elapsed();
    println!("HashMap sum: {}, time: {:?}", sum_map, duration_map);

    // 驗證加總結果
    assert_eq!(sum_vec, sum_map);
}

Vec sorted sum: 499500, time: 13.12µs
HashMap sum: 499500, time: 462.583µs

結論

如果Hashmap可以轉成向量來操作會快很多，因此在leetcode中處理已知範圍類型的題目，我們可以用頻率陣列來替代hashmap，來解個幾題。

leetcode 242 Valid Anagram

題目：判斷字串中的字元能否重組，比較每個字母出現頻率是否相同

輸入：s = "anagram", t = "nagaram"

輸出 ：true

限制：

• 1 <= s.length, t.length <= 5 * 10^4

• s and t 只包含英文小寫

頻率陣列解法：因為只有小寫字母因此只要宣告2個各26 bytes大小的陣列，一個迴圈跑完所有字串，比較陣列是否相等

impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {

        if(s.len()!=t.len()){
            return false
        }

        let mut v_s = [0;26];
        let mut v_t = [0;26];

        for (si,ti) in s.bytes().zip(t.bytes()) {
            v_s[(si-b'a') as usize] +=1;
            v_t[(ti-b'a') as usize] +=1;
        }
        v_s==v_t
    }
}

leetcode 1657. Determine if Two Strings Are Close

題目：比較兩字串是否相近，判斷方式

1. 可以透過交換字元組成相同字串
2. 可以透過交換字元出現頻率組成相同字串，符合上述2種即是相近字串。

輸入：word1 = "cabbba", word2 = "abbccc"

輸出：true

限制：

• 1 <= word1.length, word2.length <= 10^5

• word1 and word2 只包含英文小寫

頻率陣列解法：將字串轉成頻率陣列，比較出現字母是否一樣和出現頻率分佈是否相等。

1. word1="cabbba":c和b頻率交換 -> "baccca"
2. word1="baccca":第一個c和第二個a位置交換 -> "baaccc"
3. word1="baaccc":b和a頻率交換 -> "abbccc"

impl Solution {
    pub fn close_strings(word1: String, word2: String) -> bool {
        if word1.len() != word2.len() {
            return false
        }
        let mut v_word1 = [0;26];
        let mut v_word2 = [0;26];

        for (b1,b2) in word1.bytes().zip(word2.bytes()){
            v_word1[(b1-b'a') as usize] +=1;
            v_word2[(b2-b'a') as usize] +=1;
        }

        for i in 0..26{
            if((v_word1[i]>0)!=(v_word2[i]>0)){
                return false
            }
        }

        v_word1.sort();
        v_word2.sort();

        v_word1==v_word2
    }
}

Day7 總結

1.時間複雜度算法
2.已知範圍的類型，可用頻率陣列來替代hashmap

參考資料

1. https://neetcode.io/courses/lessons/big-o-notation