368 Largest Divisible Subset
1. Question
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si% Sj= 0 or Sj% Si= 0.
If there are multiple solutions, return any subset is fine.
Example 1:
nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)
Example 2:
nums: [1,2,4,8]
Result: [1,2,4,8]
2. Implementation
思路: 因为要找的是最大的subset,我们发现最后我们要找的结果和它当前的位置是无关的,所以为了方便比较,我们先对输入的数组排序。然后我们用类似于找Longest Increasing Subsequence的方式找到最大的divisible subset。我们用count和preIndex两个数组分别记录以下信息: count[i]表示在位置i之前的,最大的divisible subset的size,preIndex[i]记录i之前的上一个divisible subset的元素。比如如果 nums[i] % nums[j] == 0 and j < i, preIndex[i] = j. 最后有一点要注意的是,如果subset只有1个元素,那么很明显这是个合法的解(自己余自己等于0),所以第一个for loop里我们先从i = 0开始,而不是i = 1
(1) DP
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
List<Integer> res = new ArrayList();
if (nums == null || nums.length == 0) {
return res;
}
Arrays.sort(nums);
int n = nums.length;
int[] dp = new int[n];
int[] preIndex = new int[n];
int maxLen = 0, index = -1;
Arrays.fill(dp, 1);
Arrays.fill(preIndex, -1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
preIndex[i] = j;
}
}
if (maxLen < dp[i]) {
maxLen = dp[i];
index = i;
}
}
while (index != -1) {
res.add(nums[index]);
index = preIndex[index];
}
return res;
}
}
3. Time & Space Complexity
DP: 时间复杂度O(n^2), 空间复杂度O(n)
Last updated
Was this helpful?