專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

最近一認(rèn)證為小紅書的網(wǎng)友在網(wǎng)上發(fā)文稱小紅書今年的年終獎(jiǎng)：【績(jī)效3.75】8個(gè)月，【績(jī)效4】20個(gè)月?，【績(jī)效5】20個(gè)月?30個(gè)月期權(quán)。如果能達(dá)到績(jī)效5，基本上就相當(dāng)于50個(gè)月了，給的確實(shí)不少。

不過在評(píng)論區(qū)一認(rèn)證為前小紅書的網(wǎng)友說出了實(shí)情，去年他們部門幾百號(hào)人就一個(gè)人拿到了績(jī)效4。拿到績(jī)效4的就才一個(gè)，能拿到績(jī)效5的概率基本上為0了。不過我覺得這種不應(yīng)該叫年終獎(jiǎng)，年終獎(jiǎng)應(yīng)該是每個(gè)人都有的，這種只有少數(shù)人能拿的應(yīng)該叫獎(jiǎng)金。

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

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

問題描述

來源：LeetCode第31題

難度：中等

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

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

示例1：

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

示例2：

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

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 100

問題分析

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

那么這題的規(guī)律該怎么找呢，我們來看這樣一組數(shù)字

[7,5,4,3,2]

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

再來看一組數(shù)字

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

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

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

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

因?yàn)?后面的數(shù)字[7,6,4,3,2]從后往前是升序的，我們只需要把他反轉(zhuǎn)即可，所以[1,4,7,6,5,3,2]的下一個(gè)排列是[1,5,2,3,4,6,7]，畫個(gè)圖來加深一下理解。

JAVA：

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

Python：

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

筆者簡(jiǎn)介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁(yè)的PDF算法文檔 。