專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近一認證為小紅書的網友在網上發文稱小紅書今年的年終獎：【績效3.75】8個月，【績效4】20個月?，【績效5】20個月?30個月期權。如果能達到績效5，基本上就相當于50個月了，給的確實不少。

不過在評論區一認證為前小紅書的網友說出了實情，去年他們部門幾百號人就一個人拿到了績效4。拿到績效4的就才一個，能拿到績效5的概率基本上為0了。不過我覺得這種不應該叫年終獎，年終獎應該是每個人都有的，這種只有少數人能拿的應該叫獎金。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第31題：下一個排列。

問題描述

來源：LeetCode第31題

難度：中等

實現獲取下一個排列的函數，算法需要將給定數字序列重新排列成字典序中下一個更大的排列（即，組合出下一個更大的整數）。如果不存在下一個更大的排列，則將數字重新排列成最小的排列（即升序排列）。

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

示例1：

輸入：nums = [1,2,3] 輸出：[1,3,2]

示例2：

輸入：nums = [3,2,1] 輸出：[1,2,3]

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 100

問題分析

這題說的是計算數字序列重新排列成 字典序中下一個更大的排列 。舉個例子，比如數字213的下一個排列是231，231的下一個排列是312。

那么這題的規律該怎么找呢，我們來看這樣一組數字

[7,5,4,3,2]

這些數字從后往前都是升序的，無論怎么調換位置都不可能獲得更大的排列。

再來看一組數字

[1,4,7,6,5,3,2]

從后往前看2→3→5→6→7是升序的，但7→4是降序的，我們只需要把4和7交換一下就可以獲得比原來更大的排列。但這里要等一下，題中要求的是找出比原來大的最小的排列。交換4和7雖然比原來大，但不是最小的。實際上用5和4交換要比7和4交換更小。

所以這里當我們從后往前找到第一個降序的數字之后（比如上面的4），我們還要從后往前找到第一個比降序數字大的值（比如上面的5），然后這兩個數字交換（比如上面的4和5交換）。

交換完之后（比如上面的交換之后是[1,5,7,6,4,3,2]），這個排列肯定是比原來的大，因為5比4大，我們只需要讓5后面的排列數字最小即可。

因為5后面的數字[7,6,4,3,2]從后往前是升序的，我們只需要把他反轉即可，所以[1,4,7,6,5,3,2]的下一個排列是[1,5,2,3,4,6,7]，畫個圖來加深一下理解。

JAVA：

public void nextPermutation(int[] nums) {     int left = nums.length - 2;     // 兩兩比較，從后面往前找第一個降序的     while (left >= 0 && nums[left] >= nums[left + 1])         left--;     // 如果數組nums中的元素都是倒敘，那么left就等于-1     if (left >= 0) {         int right = nums.length - 1;         // 從后面查找第一個比nums[left]大的值         while (nums[right] <= nums[left])             right--;         swap(nums, left, right);     }     // 反轉后面升序的數字     reverse(nums, left + 1, nums.length - 1); } // 反轉子數組[left，right]中的元素 private void reverse(int[] nums, int left, int right) {     while (left < right)         swap(nums, left++, right--); } // 交換數組中的兩個數字 private void swap(int[] nums, int left, int right) {     int tmp = nums[left];     nums[left] = nums[right];     nums[right] = tmp; }

C++：

public:     void nextPermutation(vector

  &nums) {         int left = nums.size() - 2;         // 兩兩比較，從后面往前找第一個降序的         while (left >= 0 && nums[left] >= nums[left + 1])             left--;         // 如果數組nums中的元素都是倒敘，那么left就等于-1         if (left >= 0) {             int right = nums.size() - 1;             // 從后面查找第一個比nums[left]大的值             while (nums[right] <= nums[left])                 right--;             swap(nums[left], nums[right]);         }         // 反轉后面升序的數字         reverse(nums.begin() + left + 1, nums.end());     }

Python：

def nextPermutation(self, nums: List[int]) -> None:     left = len(nums) - 2     # 兩兩比較，從后面往前找第一個降序的     while left >= 0 and nums[left] >= nums[left + 1]:         left -= 1     # 如果數組nums中的元素都是倒敘，那么left就等于-1     if left >= 0:         right = len(nums) - 1         # 從后面查找第一個比nums[left]大的值         while nums[right] <= nums[left]:             right -= 1         # 交換nums[left]和nums[right]         nums[left], nums[right] = nums[right], nums[left]     # 反轉后面升序的數字     nums[left + 1:] = reversed(nums[left + 1:])

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。