LeetCode 3217. Delete Nodes From Linked List Present in Array

https://leetcode.com/problems/delete-nodes-from-linked-list-present-in-array/description/

題目大意

給一個 linked list 跟整數陣列 nums
把 nums 中有出現的數字從 linked list 中移除並回傳新的串列頭

Constraints:

• $1\le$ nums.length
  $\le {10}^5$
• $1\le$ nums[i]
  $\le {10}^5$
• nums 中的元素全相異
• linked list 中的元素值範圍在
  $[1,{10}^5]$.
• $1\le$ Node.val
  $\le {10}^5$
• 測資提供的 linked list 必至少一個節點的值不在 nums 中

思考

這題不難，兩個重點會就輕輕鬆鬆

1. 快速查找節點值是否在 nums 中
2. 刪除節點

這邊再次給不熟悉資料結構的做簡單說明

先談查找，以時間複雜度作為理論依據來說，我們要在陣列中尋找到某個值的時間複雜度是

$O(m)$ ，其中 m 為 nums.size()
我們要想刪除 linked list 中的節點，由於我們只有 head 的位置，所以我們勢必要從頭到尾遍歷 linked list 一遍，若 linked list 長度為 n 則我們每到達一個節點就要花費

$O(m)$ 的時間確認 Node.val 是否在 nums 中
這樣的時間複雜度是

$O(mn)$

所以一個相當直觀的想法是，我們可以事先確認 nums 都有哪些值

如果我們使用 unordered_set 來記錄：

unordered_set<int> numSet(nums.begin(), nums.end());

插入的平均時間複雜度為

$O(1)$ ，所以建立表的時間是

$O(m)$
查找的平均複雜度我們也能視為

$O(1)$ ，遍歷的時候我們每次只花

$O(1)$，所以我們所以查找整條 linked list 也就花

$O(n)$

numSet.find(curr->next->val) != numSet.end() // set 的查找，如果沒找到，值就會是 numSet.end()

時間複雜度這樣下來變成了

$O(m+n)$

以演算法來說，回答到這就已經相當不錯，可以交卷了
不過使用 unordered_set 有個問題，那就是它的原理實際依賴 hash table ，這個的原理簡單來說就是透過設計好的 hash function 在平均來說

$O(1)$ 之下得到資料的索引
然而，在最壞的情況下，查找可能會退化回線性

由於這題我們只是需要知道 Node.val 是否在 nums 中
所以一個更好的選擇是用 bitset

時間複雜度來看兩個選擇的演算法是一樣的
然而以這題來說，我們會發現基於位運算的 bitset 時間表現上會更好一些

以下為最後的參考解答

class Solution
{
public:
    ListNode *modifiedList(vector<int> &nums, ListNode *head)
    {
        bitset<100001> bitSet;

        for (int num : nums)
        {
            bitSet.set(num);
        }

        ListNode *dummy = new ListNode(0, head);
        ListNode *curr = dummy;

        while (curr->next)
        {
            if (bitSet[curr->next->val])
                curr->next = curr->next->next;
            else
                curr = curr->next;
        }

        return dummy->next;
    }
};

這邊用了 linked list 的一個小技巧，就是設一個 dummy node (在 head 前新加一個沒有要用的節點，這樣我們永遠看當前節點的下一個節點就好，也就是 curr->next)
這樣下面寫 code 會比較簡潔好寫