LeetCode 368. Largest Divisible Subset.jpg
LeetCode 368. Largest Divisible Subset
Description
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:
Input: [1,2,3]
Output: [1,2] (of course, [1,3] will also be ok)
Example 2:
Input: [1,2,4,8]
Output: [1,2,4,8]
描述
给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。
如果有多个目标子集，返回其中任何一个均可。
示例 1:
输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)
示例 2:
输入: [1,2,4,8]
输出: [1,2,4,8]
思路
- 这道题目的做法借鉴了第 300 题 Longest Increasing Subsequence 的思路。
- 对数组从小到大排序；
- 我们首先求得在给定的数组中，满足条件的数构成的新数组的长度；然后再去求得对应的数组是什么；
- 声明一个 count 数组，count[i] 表示给定数组 num 中，以数字 num[i] 作为结尾能够形成的满足条件的最大数组长度；
- 声明一个 path 数组，用于记录数字 num[i] 的上一个有效数字的索引；
- 因为在求 count[i] 时，我们会遍历 num[i-1] 到 num[0], 如果 num[i] % num[j] ==0 (j 的范围是 [i-1,0]); 那么 count[i] = max(count[i],count[j]+1)；并且如果 count[j]+1 更大，说明 nums[i] 可以追加到 num[j] 后面，于是更新 path[i]=j;
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-06-14 11:17:30
# @Last Modified by: 何睿
# @Last Modified time: 2019-06-14 13:09:36
from typing import List
class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
if not nums: return []
# max_count 用于记录满足条件的数构成的数组的最大长度
# end 用于记录满足条件的数的最后一个数的索引
max_count, end = 1, 0
count, path = [1] * len(nums), [0] * len(nums)
nums.sort()
for i in range(1, len(nums)):
for j in range(i - 1, -1, -1):
# 确定数字num[i] 可以追加到前面的哪一个数字中
if nums[i] % nums[j] == 0 and count[j] + 1 > count[i]:
count[i] = count[j] + 1
path[i] = j
# 如果当前的数比 max_count,说明 nums[i] 是的需要的结果数组扩大了
# 记下 i 的位置
if count[i] >= max_count:
max_count = count[i]
end = i
res = []
for _ in range(max_count):
res.append(nums[end])
end = path[end]
return res
