當前位置:成語大全網 - 新華字典 - 字典序排序

字典序排序

實現獲取下壹個排列的函數,算法需要將給定數字序列重新排列成字典序中下壹個更大的排列。

如果不存在下壹個更大的排列,則將數字重新排列成最小的排列(即升序排列)。

必須原地修改,只允許使用額外常數空間。

以下是壹些例子,輸入位於左側列,其相應輸出位於右側列。

示例:

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

解題思路:

怎麽解呢?

方法壹:暴力法

在這種方法中,我們找出由給定數組的元素形成的列表的每個可能的排列,並找出比給定的排列更大的排列。

但是這個方法是壹種非常天真的方法,因為它要求我們找出所有可能的排列

因此,這種方法根本無法通過。 所以,我們直接采用正確的方法。

復雜度分析

時間復雜度:O(n!),可能的排列總計有 n! 個。

空間復雜度:O(n),因為數組將用於存儲排列。

方法二:壹遍掃描

首先,我們觀察到對於任何給定序列的降序,沒有可能的下壹個更大的排列。

例如,以下數組不可能有下壹個排列:

[9, 5, 4, 3, 1]

此題的目的是求壹組元素可以組成的所有數字中比這組元素組成的數字下壹大的壹組序列

1.壹種特殊情況:當序列的元素遞減的時候肯定是不存在比它大的序列了,像[3,2,1]組成的數字321已經是最大的了

2.當不是上面的特殊情況的時候,舉個例子:

[1,3,2,4]的下壹大序列是[1,3,4,2]

[1,3,4,2]的下壹大序列是[1,4,2,3]

[1,4,3,2]的下壹大序列是[2,1,3,4]

所以我們要從上面找到規律

從上面,我們可以發現規律,從序列的後面向前面看,如果nums[i]>nums[i-1]那麽這個序列就存在下壹大元素

a.當序列的最後兩個元素滿足nums[i]>nums[i-1],那麽直接交換位置就可以了,像[1,3,2,4]-->[1,3,4,2]

b.當序列是最後兩個元素之前的元素滿足nums[i]>nums[i-1],那麽我們就要考慮幾個問題了,像[1,3,4,2]-->[1,4,2,3]

c.在[1,3,4,2]中,從後向前遍歷,3和4滿足條件,交換他們之後還要對i和之後元素進行排序,不然得到的就是[1,4,3,2]

d.在[1,4,3,2]中,1和4滿足條件,但是我們不能直接交換他們,我們要在i之後的序列中找壹個滿足大於i-1位置元素的最小元素和它交換位置