亚洲色图一区二区三区,五月天av伊人av,日韩视频在线观看二区,国产黄色片精品AAWWW,欧美成人免费观看视频,国产一区二区三区四区五区在线,亚洲最大的成人网址,91成人精品一区在线播放

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做下一個排列，我們先來看題面：

https://leetcode-cn.com/problems/next-permutation/

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

題意

實(shí)現(xiàn)獲取下一個排列的函數(shù)，算法需要將給定數(shù)字序列重新排列成字典序中下一個更大的排列。

如果不存在下一個更大的排列，則將數(shù)字重新排列成最小的排列（即升序排列）。

樣例

一些例子，輸入位于左側(cè)列，其相應(yīng)輸出位于右側(cè)列。
1,2,3?→?1,3,2
3,2,1?→?1,2,3
1,1,5?→?1,5,1

題解

從數(shù)組最后一個元素開始掃描，尋找到nums[i] > nums[i - 1]的第一個i值。如果得到i值大于等于1，說明數(shù)組存在下一個排列。

a.我們還是從數(shù)組最后一個元素開始掃描，尋找到num[j] > nums[i - 1]的第一個j值。由于nums[i] > nums[i - 1]，所以我們的j值一定是大于等于i的

b.交換索引為i - 1和索引為j的元素的值。

c.此時(shí)索引i及之后的排列時(shí)一個降序排列，將其變成升序排列即可。

為什么說此時(shí)索引i及之后的排列是一個降序排列呢？

對于原來的數(shù)組，由于我們是從數(shù)組最后一個元素開始掃描尋找到的nums[i] > nums[i - 1]的第一個i值，我們原數(shù)組中i之后的排列一定是一個降序排列。那么我們只需要看交換之后是否依然是一個降序排列呢？

而尋找索引j，我們還是從數(shù)組最后一個元素開始掃描，尋找到num[j] > nums[i - 1]的第一個j值。對于索引j之后的值，一定是小于等于nums[i - 1]的。對于而對于索引i到j(luò) - 1這部分元素，一定是大于等于num[j]的，自然一定大于nums[i - 1]，那么，交換之后，原數(shù)組中i之后的排列一定依然是一個降序排列。

（3）如果得到的i值小于1，說明數(shù)組不存在下一個排列，倒序輸出數(shù)組即得升序排列。

public?class?Solution?{
?
??public?void?nextPermutation(int[] nums)?{
????int?n = nums.length;
????int?i = n - 1;
????for(; i >= 1; i--) {
??????if(nums[i] > nums[i - 1]) {
????????break;
??????}
????}
????if(i >= 1) {
??????int?j = n - 1;
??????for(; j >= i; j--) {
????????if(nums[j] > nums[i - 1]) {
??????????break;
????????}
??????}
??????swap(i - 1, j, nums);
??????reverse(nums, i);
????}else?{
??????reverse(nums, 0);
????}
??}
??
??private?void?reverse(int[] nums, int?index)?{
????int?i = index;
????int?j = nums.length - 1;
????while(i < j) {
??????swap(i, j, nums);
??????i++;
??????j--;
????}
??}
?
??private?void?swap(int?i, int?j, int[] nums)?{
????int?temp = nums[i];
????nums[i] = nums[j];
????nums[j] = temp;
??}
}