单位建设网站硬件,网站建设的规模设想,网站建设遵循的规范,做网站推荐源创网络文章目录摘要描述题解答案题解代码分析代码拆解示例测试及结果时间复杂度空间复杂度总结摘要
有时候我们会遇到这样的问题#xff1a;给定一堆数#xff0c;如何从中挑出一个子集#xff0c;让这个子集里的每一对数都能互相整除#xff1f;题目要求我们找出最大的这样一个… 文章目录摘要描述题解答案题解代码分析代码拆解示例测试及结果时间复杂度空间复杂度总结摘要
有时候我们会遇到这样的问题给定一堆数如何从中挑出一个子集让这个子集里的每一对数都能互相整除题目要求我们找出最大的这样一个子集。
这个问题看起来有点像是在“组团”条件是必须能整除。其实背后是一个动态规划问题用来锻炼我们对“子问题递推”的理解。 描述
题目给了一个数组 nums里面是一些互不相同的正整数。我们要找出一个最大的子集 answer使得里面的任意两个数 a 和 b 满足
a % b 0或者b % a 0。
换句话说要么一个能被另一个整除要么反过来也能被整除。
示例 1
输入: [1,2,3]
输出: [1,2]
解释: 其实 [1,3] 也对因为 3 % 1 0。示例 2
输入: [1,2,4,8]
输出: [1,2,4,8]题解答案
直观的思路是
如果一个数可以整除另一个数那它们更可能属于同一个子集。子集要尽量大所以我们需要在多个候选方案中找到“最长的那条链”。
动态规划的做法 先把数组排序因为小数更容易整除大数。 用一个数组 dp[i] 表示以 nums[i] 结尾的最大整除子集的长度。 遍历每个 nums[i]再和前面的数 nums[j] 去比较 如果 nums[i] % nums[j] 0说明能放在一起那就更新 dp[i] max(dp[i], dp[j] 1)。 同时用一个 parent 数组来记录前驱方便最后回溯出完整的子集。 题解代码分析
下面是 Swift 的实现
import Foundationclass Solution {func largestDivisibleSubset(_ nums: [Int]) - [Int] {if nums.isEmpty { return [] }let nums nums.sorted()let n nums.countvar dp Array(repeating: 1, count: n) // 每个数至少能独立成一个集合var parent Array(repeating: -1, count: n) // 用来回溯路径var maxLen 1var maxIndex 0for i in 1..n {for j in 0..i {if nums[i] % nums[j] 0 {if dp[j] 1 dp[i] {dp[i] dp[j] 1parent[i] j}}}if dp[i] maxLen {maxLen dp[i]maxIndex i}}// 回溯答案var result [Int]()var k maxIndexwhile k ! -1 {result.append(nums[k])k parent[k]}return result.reversed()}
}// MARK: - Demo 演示
let solution Solution()
print(solution.largestDivisibleSubset([1, 2, 3])) // [1, 2] 或 [1, 3]
print(solution.largestDivisibleSubset([1, 2, 4, 8])) // [1, 2, 4, 8]
print(solution.largestDivisibleSubset([3, 5, 10, 20, 21])) // [5, 10, 20]代码拆解 排序 把数组排好序保证前面的数比后面的小便于判断整除关系。 动态规划数组 dp dp[i] 表示以 nums[i] 结尾的最大整除子集的长度。 前驱数组 parent parent[i] 记录了 nums[i] 前面可以接上的数字位置用来回溯结果。 两层循环 外层 i 表示当前要计算的数。内层 j 遍历比它小的数看能不能整除。 回溯结果 从最大长度的下标开始不断回溯 parent拼成最终的子集。
示例测试及结果
运行 Demo结果如下
输入: [1, 2, 3]
输出: [1, 2] // 或 [1, 3]输入: [1, 2, 4, 8]
输出: [1, 2, 4, 8]输入: [3, 5, 10, 20, 21]
输出: [5, 10, 20]这个结果是合理的比如 [5, 10, 20] 就是一条完整的整除链
10 % 5 020 % 10 0
时间复杂度
外层循环 i 最多跑 n 次内层循环 j 也最多 n 次。所以时间复杂度是 O(n²)。在 n 1000 的范围内这个复杂度是可接受的。
空间复杂度
使用了 dp 和 parent 两个数组各占 O(n)。回溯的结果也是 O(n)。所以整体空间复杂度是 O(n)。
总结
这道题的关键在于 先排序再动态规划
排序后更容易保证“整除链”的关系。动态规划帮我们一步步延长最长的整除子集。
如果用现实场景来打个比方
你可以把每个数想象成一个“圈子”只有能整除的才能成为同一个圈子。我们要找的就是那个能容纳最多成员的“最大圈子”。
这类题目训练了我们对 递推关系 的思考能力也再次证明了排序在动态规划里的重要作用。
