ETH官方钱包

前往
大廳
主題

LeetCode - 2766. Relocate Marbles 解題心得

Not In My Back Yard | 2024-09-26 12:00:18 | 巴幣 2 | 人氣 12

題目連結:


題目意譯:
你被給定一個索引值從 0 開始的整數陣列 nums 代表著若干個彈珠的初始位置。你同時也被給定兩個索引值從 0 開始且長度相同的整數陣列 moveFrom 和 moveTo。

在接著的 moveFrom.length 步,你將會改變彈珠的位置。在第 i 步時,你將會把位於位置 moveFrom[i] 上的彈珠全數移動到位置 moveTo[i]。

完成所有步驟之後,回傳一個由小排到大的「被佔用」之位置。

注:
如果在某個位置上有至少一個彈珠,則我們稱該位置為「被佔用」的。
單一位置上可以有多個彈珠。

限制:
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ moveFrom.length ≦ 10 ^ 5
moveFrom.length == moveTo.length
1 ≦ nums[i], moveFrom[i], moveTo[i] ≦ 10 ^ 9
測資之生成滿足在處理第 i 步時至少會有一個彈珠在 moveFrom[i] 上。



範例測資:
範例 1:
輸入: nums = [1,6,7,8], moveFrom = [1,7,2], moveTo = [2,9,5]
輸出: [5,6,8,9]
解釋: 一開始,各個彈珠位於位置 [1,6,7,8]。
在第 i = 0 步,我們將位於位置 1 的彈珠移動到位置 2。此時,被佔用的位置為 [2,6,7,8]。
在第 i = 1 步,我們將位於位置 7 的彈珠移動到位置 9。此時,被佔用的位置為 [2,6,8,9]。
在第 i = 2 步,我們將位於位置 2 的彈珠移動到位置 5。此時,被佔用的位置為 [5,6,8,9]。
最後,有至少一個彈珠的位置為 [5,6,8,9]。

範例 2:
輸入: nums = [1,1,3,3], moveFrom = [1,3], moveTo = [2,2]
輸出: [2]
解釋: 一開始,,各個彈珠位於位置 [1,1,3,3]。
在第 i = 0 步,我們將位於位置 1 的彈珠移動到位置 2。此時,被佔用的位置為 [2,2,3,3]。
在第 i = 1 步,我們將位於位置 3 的彈珠移動到位置 2。此時,被佔用的位置為 [2,2,2,2]。
由於 2 是唯一一個被佔用的位置,我們回傳 [2]。


解題思維:
善用雜湊表(Hash Table)。然後直接模擬每一步彈珠的移動位置即可。而且甚至不需要統計數量。因為題目只在乎位置,因此只存位置資訊即可。

最後把表中的「還存在」的位置拉出來塞進一個陣列並由小排到大即是所求。




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

創作回應

相關創作

更多創作