主題

LeetCode - 565. Array Nesting 解題心得

Not In My Back Yard | 2021-11-24 00:00:01 | 巴幣 0 | 人氣 134

題目連結:


題目意譯:
你被給定一個長度為 n 的整數陣列 nums,其中 nums 為範圍 [0, n - 1] 這些數字的一種排列。

你應建立一個集合 s[k] = { nums[k], nums[nums[k]], nums[nums[nums[k]]], …… } 符合以下規則:
s[k] 的第一個元素應使於選擇索引值 = k 之元素 nums[k]。
s[k] 中的下一個元素將會是 nums[nums[k]],以及 nums[nums[nums[k]]]……以此類推。

我們將在會有重複元素出現於 s[k] 前停止。

回傳集合 s[k] 最長長度。

限制:
1 ≦ nums.length ≦ 10 ^ 5
0 ≦ nums[i] < nums.length
nums 中所有值相異。



範例測資:
範例 1:
輸入: nums = [5,4,0,3,1,6,2]
輸出: 4
解釋:
nums[0] = 5 、 nums[1] = 4 、 nums[2] = 0 、 nums[3] = 3 、 nums[4] = 1 、 nums[5] = 6 、 nums[6] = 2。
其中一個最長的集合 s[k]:
s[0] = { nums[0], nums[5], nums[6], nums[2] } = { 5, 6, 2, 0 }

範例 2:
輸入: nums = [0,1,2]
輸出: 1


解題思維:
可以看到集合 s[k] 改為以其中任一個元素開頭都會產生有著相同內容的集合。例如範例 1 的 [5,4,0,3,1,6,2] 之
s[0] = { nums[0], nums[5], nums[6], nums[2] } = { 5, 6, 2, 0 }
s[5] = { nums[5], nums[6], nums[2], nums[0] } = { 6, 2, 0, 5 }
s[6] = { nums[6], nums[2], nums[0], nums[5] } = { 2, 0, 5, 6 }
s[2] = { nums[2], nums[0], nums[5], nums[6] } = { 0, 5, 6, 2 }

因此我們利用一個長度為 n 的布林陣列 H[i] 來判斷 nums[i] 是否已經存在於任一個現存的集合之中。因此我們掃過 nums 每個位置 nums[i],當 H[i] 為否時代表 nums[i] 還沒有屬於它的集合存在。因此我們從 nums[i] 開始,將 nums[i] 、 nums[nums[i]] 等等之相應 H 之位置設為真(以示這些元素已存於某集合中)。

而我們能擴展到的元素之個數即是該集合的長度。且根據先前的事實:「集合中任一元素都可作為開頭並產生同內容之集合」。我們可以知道我們掃完 nums 後便可以得到所有可能的集合。因此這些集合中最長的長度之值即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作