LeetCode 368----Largest Divisible Subset

原題連結: 368. Largest Divisible Subset

Given a set of distinct positive integers

nums

, return the largest subset

answer

such that every pair

(answer[i], answer[j])

of elements in this subset satisfies:

• answer[i] % answer[j] == 0

  , or

• answer[j] % answer[i] == 0

If there are multiple solutions, return any of them.

Example 1:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.
           

Example 2:

Input: nums = [1,2,4,8]
Output: [1,2,4,8]
           

Constraints:

• 1 <= nums.length <= 1000

• 1 <= nums[i] <= 2 * 109

• All the integers in

  nums

  are unique.

算法分析

首先想到要對數組進行升序排序

從小向大周遊數組。假設數字

b % a == 0

，那麼可以考慮将數字

b

加入到包含

a

的連結清單裡，

b

的字首就是

a

；最終，我們挑選出長度最大的那個連結清單，将其中的全部數字放入到一個數組中，即可得到答案。

但我們并不是找到任意一個滿足

b % a == 0

的

a

後，就立即将

b

加入到對應的連結清單裡，而是應該選擇

b

的全部約數中的最長的連結清單，将

b

加入該連結清單尾部。

直接使用連結清單，不友善在O(1)的時間内直接得到連結清單的長度，是以我們可以建立一個數組 linkLen，linkLen[i] 即表示以 nums[i] 作為尾節點的連結清單的長度。另外，我們建立一個數組 parent，parent[i] 即表示 nums[i] 所在連結清單的字首節點在 nums 數組的下标。如果 parent[i] == i，那麼表示 nums[i] 是這個數組的頭結點 ---- 沒有字首節點了。

這裡需要使用數學歸納法證明一下，我們将

b

加入到其所有約數中長度最大的連結清單中的正确性：

記

将數字nums[i]加入到其全部約數中長度最大的連結清單尾部

為

規則x

初始令全部 linkLen[i] = 0

• (1) 對于 nums 中的第一個nums[0]，其沒有字首數字，是以作為連結清單頭結點，有 parent[0] = 0，linkLen[0] = 1; 此時，最長連結清單即為 linkLen 中數字最大的元素對應的下标i，即 i = 0;

  規則x

  正确；
• (2) 假設當 i = k (k > 0)，

  規則x

  得到的 parent、linkLen 數組滿足我們的要求 ---- 即 linkLen 數組中最大元素的下标，就是最長連結清單的尾節點元素在 nums 中的下标，假設該下标值為 index_k（至少有 linkLen[index_k] >= 1)。

  那麼當 i = k + 1 時，周遊 j = 0 ~ k:

  • (2.1) 如果全部 nums[j] 均不為 nums[i] 的約數，那麼應用

    規則x

    ，nums[i] 将作為連結清單頭結點，有 parent[i] = i, linkLen[i] = 1; 此時linkLen數組最大值依然為 linkLen[index_k];

    規則x

    正确。
  • (2.2) 如果某個 nums[j] 為 nums[i] 的約數，我們令 parent[i] = j, linkLen[i] = linkLen[j] + 1，那麼：
    • (2.2.1) 如果 j == index_k，那麼 linkLen[i] = linkLen[index_k] + 1，此時 linkLen[i] 為 linkLen 數組中的最大元素；

      規則x

    • (2.2.2) 如果 j != index_k，那麼 nums[index_k] 就不是 nums[i] 的約數，nums[i] 對以 nums[index_k] 為尾結點的連結清單無影響。linkLen[i] 或 linkLen[index_k] 為數組 linkLen 中的最大元素；

      規則x

綜上所述，應用

規則x

，我們得到的 linkLen 數組，其最大元素對應的下标為i，那麼以 nums[i] 為尾結點的連結清單即為最長連結清單。

算法實作 Golang

func largestDivisibleSubset(nums []int) []int {
	sort.Sort(sort.IntSlice(nums))
	N := len(nums) // 元素個數
	parent := make([]int, N) // 使用類似并查集的算法，但是不對該并查集進行壓縮
	linkLen := make([]int, N)
	maxLen := 0 // 最大連結清單長度
	maxIndex := -1 // 最大連結清單尾結點元素在 nums 數組中的下标
	for i, val := range nums {
		parent[i] = i // 預設目前元素沒有約數，則其字首節點即為自身
		linkLen[i] = 1 // 目前元素預設作為頭結點，連結清單長度為 1
		for j := 0; j < i && (val/nums[j] >= 2); j++ { // 因為 nums 數組是升序的，是以對于 val/nums[j] < 2 的 j 就無需再周遊了
			if val%nums[j] == 0 {
				if linkLen[j]+1 > linkLen[i] {
					parent[i] = j
					linkLen[i] = linkLen[j] + 1
				}
			}
		}
		// 内層 for 循環結束，nums[i] 即挂在到了正确的連結清單尾部

		if linkLen[i] > maxLen {
			// 記錄全部連結清單中的最長連結清單長度和其尾元素的下标
			maxLen = linkLen[i] 
			maxIndex = i
		}
	}
	cursor := maxIndex
	ans := make([]int, maxLen) 
	pos := linkLen[cursor] - 1
	for parent[cursor] != cursor { // 如果 parent[cursor] == cursor，那麼 nums[cursor] 即為連結清單頭結點
		ans[pos] = nums[cursor]
		pos--
		cursor = parent[cursor]
	}
	ans[pos] = nums[cursor] // 此時實際上 cursor = 0
	return ans
}
           

運作結果