Medium

题目描述

给定两个整数 n 和 k，将数字 n 拆分为恰好 k 个正整数，使得这些整数的乘积等于 n。

返回任意一个拆分，使得任意两个数字之间的最大差值最小。你可以以任意顺序返回结果。

示例 1：

输入：n = 100, k = 2
输出：[10,10]
解释：拆分 [10, 10] 得到 10 * 10 = 100，最大最小差值为 0，这是最小的。

示例 2：

输入：n = 44, k = 3
输出：[2,2,11]
解释：
- 拆分 [1, 1, 44] 差值为 43
- 拆分 [1, 2, 22] 差值为 21
- 拆分 [1, 4, 11] 差值为 10
- 拆分 [2, 2, 11] 差值为 9
因此，[2, 2, 11] 是差值最小的最优拆分，差值为 9。

约束条件：

  • 4 ≤ n ≤ 10^5
  • 2 ≤ k ≤ 5
  • k 严格小于 n 的正因数总数

提示：

  • 首先，计算 n 的所有正因数并将它们排序到列表 divs 中
  • 使用递归搜索 dfs(start, picked, prod, path)，从 divs[start…] 中选择下一个因数，将其乘入 prod 并附加到 path，直到有 k 个因数且乘积为 n
  • 在搜索过程中，跟踪最小化 max(path) - min(path) 的最佳 path 并返回它

解题思路

这道题要求将数字 n 分解为 k 个正整数的乘积，并使得这些数字之间的最大差值最小。

核心思路：

  1. 因数枚举：首先找出 n 的所有因数，因为只有 n 的因数才能参与有效的分解。

  2. 回溯搜索：使用深度优先搜索（DFS）来尝试所有可能的分解组合。对于每个位置，我们尝试选择不同的因数，确保剩余的乘积仍能被分解为所需数量的因数。

  3. 剪枝优化：

    • 当前乘积必须能被 n 整除
    • 剩余需要选择的数字数量要合理
    • 及时更新最优解，避免不必要的搜索

  4. 最优性判断：对于每个完整的分解方案，计算其最大值与最小值的差，保留差值最小的方案。

算法步骤：

  • 预处理得到 n 的所有因数并排序
  • 使用回溯法枚举所有可能的 k 个因数组合
  • 对每个有效组合计算差值，更新最优解
  • 返回最优分解方案

由于 k ≤ 5 且 n ≤ 10^5，搜索空间相对较小，回溯法能够有效找到最优解。

代码实现

class Solution {
public:
    vector<int> minDifference(int n, int k) {
        vector<int> divisors;
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                divisors.push_back(i);
                if (i != n / i) {
                    divisors.push_back(n / i);
                }
            }
        }
        sort(divisors.begin(), divisors.end());
        
        vector<int> best;
        int minDiff = INT_MAX;
        vector<int> current;
        
        function<void(int, int, int)> dfs = [&](int idx, int product, int remaining) {
            if (remaining == 0) {
                if (product == 1) {
                    int maxVal = *max_element(current.begin(), current.end());
                    int minVal = *min_element(current.begin(), current.end());
                    if (maxVal - minVal < minDiff) {
                        minDiff = maxVal - minVal;
                        best = current;
                    }
                }
                return;
            }
            
            if (idx >= divisors.size() || product == 0) return;
            
            for (int i = idx; i < divisors.size(); i++) {
                int div = divisors[i];
                if (product % div == 0) {
                    current.push_back(div);
                    dfs(i, product / div, remaining - 1);
                    current.pop_back();
                }
            }
        };
        
        dfs(0, n, k);
        return best;
    }
};

class Solution:
    def minDifference(self, n: int, k: int) -> List[int]:
        # Find all divisors of n
        divisors = []
        i = 1
        while i * i <= n:
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)
            i += 1
        divisors.sort()
        
        best = []
        min_diff = float('inf')
        
        def dfs(idx, product, remaining, path):
            nonlocal best, min_diff
            
            if remaining == 0:
                if product == 1:
                    max_val = max(path)
                    min_val = min(path)
                    if max_val - min_val < min_diff:
                        min_diff = max_val - min_val
                        best = path[:]
                return
            
            if idx >= len(divisors) or product == 0:
                return
            
            for i in range(idx, len(divisors)):
                div = divisors[i]
                if product % div == 0:
                    path.append(div)
                    dfs(i, product // div, remaining - 1, path)
                    path.pop()
        
        dfs(0, n, k, [])
        return best

public class Solution {
    public int[] MinDifference(int n, int k) {
        List<int> divisors = new List<int>();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                divisors.Add(i);
                if (i != n / i) {
                    divisors.Add(n / i);
                }
            }
        }
        divisors.Sort();
        
        List<int> best = new List<int>();
        int minDiff = int.MaxValue;
        List<int> current = new List<int>();
        
        void Dfs(int idx, int product, int remaining) {
            if (remaining == 0) {
                if (product == 1) {
                    int maxVal = current.Max();
                    int minVal = current.Min();
                    if (maxVal - minVal < minDiff) {
                        minDiff = maxVal - minVal;
                        best = new List<int>(current);
                    }
                }
                return;
            }
            
            if (idx >= divisors.Count || product == 0) return;
            
            for (int i = idx; i < divisors.Count; i++) {
                int div = divisors[i];
                if (product % div == 0) {
                    current.Add(div);
                    Dfs(i, product / div, remaining - 1);
                    current.RemoveAt(current.Count - 1);
                }
            }
        }
        
        Dfs(0, n, k);
        return best.ToArray();
    }
}

var minDifference = function(n, k) {
    function getDivisors(num) {
        const divisors = [];
        for (let i = 1; i <= Math.sqrt(num); i++) {
            if (num % i === 0) {
                divisors.push(i);
                if (i !== num / i) {
                    divisors.push(num / i);
                }
            }
        }
        return divisors.sort((a, b) => a - b);
    }
    
    function backtrack(remaining, factorsLeft, currentFactors) {
        if (factorsLeft === 0) {
            if (remaining === 1) {
                return [...currentFactors];
            }
            return null;
        }
        
        if (factorsLeft === 1) {
            currentFactors.push(remaining);
            return [...currentFactors];
        }
        
        const divisors = getDivisors(remaining);
        let bestResult = null;
        let minDiff = Infinity;
        
        for (const divisor of divisors) {
            if (divisor > remaining) break;
            
            currentFactors.push(divisor);
            const result = backtrack(remaining / divisor, factorsLeft - 1, currentFactors);
            
            if (result) {
                const diff = Math.max(...result) - Math.min(...result);
                if (diff < minDiff) {
                    minDiff = diff;
                    bestResult = [...result];
                }
            }
            
            currentFactors.pop();
        }
        
        return bestResult;
    }
    
    return backtrack(n, k, []);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(d^k)，其中 d 是 n 的因数个数，通常 d = O(√n)，k ≤ 5
空间复杂度O(d + k)，用于存储因数列表和递归栈空间