題目資訊

題目編號: 368
題目連結: Largest Divisible Subset
主題: Array, Math, Dynamic Programming, Sorting

題目敘述

給定一組不同的正整數 nums，返回最大的子集 answer，使得此子集中的每一對元素 (answer[i], answer[j]) 都滿足：

answer[i] % answer[j] == 0，或者
answer[j] % answer[i] == 0

如果存在多個解，返回其中任一個即可。

範例 1:

輸入: nums = [1,2,3]
輸出: [1,2]
解釋: [1,3] 也被接受。

範例 2:

輸入: nums = [1,2,4,8]
輸出: [1,2,4,8]

限制條件:

$1 \leq nums.length \leq 1000$
$1 \leq nums[i] \leq 2 \times 10^9$
nums 中的所有整數都是唯一的。

直覺

此問題要求找出一個由給定的相異正整數組成的最大子集，使得子集中的每一對數字都滿足可整除條件。直覺上，首先對數組進行排序，這樣能夠方便地檢查可整除的條件，因為若一個數能被另一個數整除，那麼這兩個數必須遵循遞增的次序。此算法採用動態規劃，以有效地計算以每個索引結尾的最大可整除子集的大小，這樣能夠在計算小索引的結果的基礎上構建出大的解。

解法

排序：首先對數組進行排序。排序簡化了問題，因為我們只需要檢查過去的數字，而不是在兩個方向上都檢查。
動態規劃準備：
- 我們初始化一個 dp 陣列，其中 dp[i] 代表以索引 i 结尾的最大可整除子集的大小。
- 同時，我們初始化一個 subsets 向量，其中每個元素都是一個集合，用於追蹤每個數字對應的最大子集中的實際元素。
將每個數初始化為單元素子集：
- 起初，每個數字都形成一個自身的子集，因此 dp[i] 起始值為 1，每個 subsets 中的集合開始時都包含對應的數字。
動態規劃計算：
- 對於索引 i 的每個數字，檢查所有之前的數字（從索引 0 到 i-1）。
- 如果 nums[i] 能被 nums[j] 整除，嘗試將以 nums[j] 結尾的最大子集擴展至包含 nums[i]。
- 這涉及檢查將 nums[i] 添加到以 nums[j] 結尾的子集中，是否會產生比當前記錄的以 dp[i] 結尾的子集更大的子集。
子集構建：
- 如果通過某個數字找到較大的子集，則更新 dp[i] 並將對應的子集中元素從 subsets[j] 添加到 subsets[i]。
- 在全體索引的迭代過程中，保持追蹤最大的子集出現的索引。
結果構建：
- 然後，直接從 subsets 向量中使用計算出的最大子集索引檢索該最大子集。
- 將這個集合轉換為一個向量，並將其作為結果返回。

此演算法有效利用了排序、動態規劃和集合，來高效地發現並存儲不僅是候選子集的大小，還有它們本身的元素。此計算的複雜度主要受到遍歷和比較子集的循環的支配，導致總體時間複雜度為 $O(n^2)$。

程式碼

C++

class Solution {

public:
    // 輔助函式，用於計算以索引 'idx' 結尾的最大子集大小
    int calc(vector<int>& nums, vector<int>& dp, vector<set<int>>& subsets, int idx) {
        // 如果已經計算過該值，直接返回
        if (dp[idx] != -1) {
            return dp[idx];
        }
        
        // 初始化當前子集大小為 1（至少包含數字本身）
        dp[idx] = 1;
        int maxSubsetIdx = -1;

        // 找到一個之前的數字，該數字能被 nums[idx] 整除，以形成更大的子集
        for (int i = 0; i < idx; ++i) {
            if (nums[idx] % nums[i] == 0 && 
                (maxSubsetIdx == -1 || calc(nums, dp, subsets, maxSubsetIdx) < calc(nums, dp, subsets, i))) {
                maxSubsetIdx = i;
            }
        }
        
        // 如果找到更大的子集，更新當前 dp 值
        if (maxSubsetIdx != -1) {
            dp[idx] += dp[maxSubsetIdx];
            subsets[idx].insert(subsets[maxSubsetIdx].begin(), subsets[maxSubsetIdx].end());
        }
        return dp[idx];
    }

    // 主函式，用於尋找最大可整除子集
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        
        // 將數字排序以便於子集檢查
        sort(nums.begin(), nums.end());
        
        // 初始化 DP 和子集數組
        vector<int> dp(n, -1);
        vector<set<int>> subsets(n);

        // 初始時每個數字形成一個單元素子集
        for (int i = 0; i < n; ++i) {
            subsets[i].insert(nums[i]);
        }

        int largestSubsetIdx = 0; // 已找到的最大子集的索引

        // 為每個數字計算最大子集
        for (int i = 0; i < n; ++i) {
            if (calc(nums, dp, subsets, i) > dp[largestSubsetIdx]) {
                largestSubsetIdx = i;
            }
        }

        // 返回找到的最大子集
        return vector<int>(subsets[largestSubsetIdx].begin(), subsets[largestSubsetIdx].end());
    }
};

Python

class Solution:

    # 輔助函式，用於計算在索引 'idx' 結尾的最大子集大小
    def calc(self, nums, dp, subsets, idx):
        # 如果已經計算過的值存在，則返回該值
        if dp[idx] != -1:
            return dp[idx]
        
        # 初始化當前子集大小為1（至少包含該數字本身）
        dp[idx] = 1
        maxSubsetIdx = -1

        # 尋找可以被 nums[idx] 整除的前一個數字以形成更大的子集
        for i in range(idx):
            if nums[idx] % nums[i] == 0 and (
                maxSubsetIdx == -1 or self.calc(nums, dp, subsets, maxSubsetIdx) < self.calc(nums, dp, subsets, i)):
                maxSubsetIdx = i
        
        # 如果找到更大的子集，更新當前 dp 的值
        if maxSubsetIdx != -1:
            dp[idx] += dp[maxSubsetIdx]
            subsets[idx].update(subsets[maxSubsetIdx])
        return dp[idx]

    # 主函式，用於找到最大的可被整除子集
    def largestDivisibleSubset(self, nums):
        n = len(nums)
        
        # 將數字排序以便於檢查子集
        nums.sort()
        
        # 初始化DP和子集陣列
        dp = [-1] * n
        subsets = [set() for _ in range(n)]

        # 最初每個數字形成一個單元素子集
        for i in range(n):
            subsets[i].add(nums[i])

        largestSubsetIdx = 0  # 記錄找到的最大子集的索引

        # 計算每個數字的最大子集
        for i in range(n):
            if self.calc(nums, dp, subsets, i) > dp[largestSubsetIdx]:
                largestSubsetIdx = i

        # 返回找到的最大子集
        return list(subsets[largestSubsetIdx])

複雜度分析

時間複雜度: $O(n^2 \log n)$
1. 排序陣列: largestDivisibleSubset 的第一步是對 nums 陣列進行排序，這需要 $O(n \log n)$ 的時間。
2. 計算 DP 值: 接下來，我們遍歷每一個元素來計算以每個索引結尾的最大子集。對於每個索引 $i$，calc 函數會遍歷每個之前的索引 $j$ 以找到可以在 $i$ 結尾的最大子集。這種嵌套遍歷導致動態規劃計算的時間複雜度為 $O(n^2)$。
3. 遞迴 calc 調用: 在每次調用 calc 時，都有可能調用到之前索引的 calc。然而，由於每個 calc(nums, dp, subsets, i) 調用結果一旦計算出來就會被儲存，這實際上意味著每個索引 $i$ 最多只有一次 calc 被計算。備忘錄方法確保這不會影響整體漸進複雜度，超出嵌套迭代。
4. 構建子集: 構建子集或將其組合起來機乎於操作數量相關，這由集合操作所支配。元素從一個集合插入到另一個集合中的複雜度被排序和迭代操作所覆蓋，這有效地攤銷到其操作上。這至多增加了一個額外的 $O(\log n)$ 因素，由於結合子集的集合屬性，在構建最終子集時，每個元素最多只考慮一次。
因此，主要操作，包括排序和評估組合，推動了時間複雜度至 $O(n^2 \log n)$。
空間複雜度: $O(n^2)$
1. DP 陣列: 我們使用大小為 n 的陣列 dp 來儲存以每個索引結尾的最大子集大小，這對空間複雜度的貢獻為 $O(n)$。
2. 子集儲存: subsets，一個集合的陣列，用於儲存各個子集。最壞情況下，每個子集可能包含所有的 n 個元素，這對空間貢獻為 $O(n^2)$。
3. 呼叫堆疊使用: 由於 calc 的遞歸性質，額外的堆疊空間會依據遞歸深度而使用。然而，遞歸的深度只延伸至每個之前的元素，因為備忘錄和每個數字僅被檢查一次，實際上深度為 $O(n)$。
總體來說，空間複雜度主要由 subsets 的儲存要求主導，結果為 $O(n^2)$ 的空間複雜度。

CS Note
En

Leetcode 368. Largest Divisible Subset

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析