主題

LeetCode - 46. Permutations 解題心得

Not In My Back Yard | 2021-09-10 00:00:03 | 巴幣 0 | 人氣 51

題目連結:


題目意譯:
給定一相異整數之陣列 nums ,回傳其所有可能的排列。你可以按照任意順序回傳答案。

限制:
1 ≦ nums.length ≦ 6
-10 ≦ nums[i] ≦ 10
nums 中所有整數皆相異。



範例測資:
範例 1:
輸入: nums = [1,2,3]
輸出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

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

範例 3:
輸入: nums = [1]
輸出: [[1]]


解題思維:
我們現在已經知道要怎麼求某個排列的「下一個排列」(Next Permuation,見這題,且根據那題的實作當有一排列沒有「下一個」時,則會將其排序)了,且我們也知道 n (nums 的長度)的相異物品的排列方式有 n! (n 階乘,即 1 × 2 × …… × n)。

因此我們執行 n! 次的「下一個排列」,即可遍歷所有可能的排列。

當然如果你不知道 n 個相異物件的排列方法數的話,你也可以先將 nums 由小到大排序,然後一直找下一個排列,直到回到由小到大排序的順序。這樣也可以遍歷所有可能的排列。




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

創作回應

相關創作

更多創作