LeetCode解題報告--Next Permutation

LeetCode解題報告--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, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
點擊解題：Next Permutation

分析：尋找給定數列的下一個排列，如果不存在，則找出該數列的初始排列。
思路：
下一個數列一定是當前數列最小增加值，即題目轉化為找出當前數列最小增量。即為下一個數列，如示意圖示：
vcr9wdC00yZsZHF1bzs1JnJkcXVvO7W9JmxkcXVvOzAmcmRxdW87tbnWw6OsvLS/yaGjyc/K9s7E19a1yLzb09qjujxiciAvPg0KKDEpLrbU09q4+Laoyv3X6W51bXMstNPT0rW91/PV0rP2bnVtc1trXSAmbHQ7IG51bXNbayAtIDFdLCBrID0gbnVtcy5sZW5ndGggLSAyIL+qyry13bz1tfy0+iwgwvrX49Kqx/O1xGsgOiBpID0gazs8YnIgLz4NCigyKS6009PStb3X89XSs/a12tK7uPa089PabnVtc1tpXbXEyv3X1m51bXNba10sayA9IG51bXMubGVuZ3RoIC0gMSC/qsq8td289bX8tPqjrML61+PSqsfztcRrIDogaiA9IGs7PGJyIC8+DQooMykuvatudW1zW2ldINPrbnVtc1tqXb27u7ssvLTPwtK7uPbFxcHQ0tSjqDGjrDOjqb+qzbc8YnIgLz4NCig0KS69q2krIDEgtb0gbnVtcy5sZW5ndGggLSAxtcTFxcHQtbnWwzwvcD4NCjxwPkphdmG0+sLro7ogQWNjZXB0ZWQ8L3A+DQo8cHJlIGNsYXNzPQ=="brush:java;"> public class Solution { public void nextPermutation(int[] nums) { //Save the first index of nums[i] < nums[k] from right to left int i = 0; //Save the first index of nums[j] > nums[i] from right to left int j = 0; //To find the first index of nums[i] < nums[k] from right to left for(int k = nums.length - 2;k > 0;k --){ if(nums[k] < nums[k + 1]){ i = k; break; } } //To find the first index of nums[j] > nums[i] from right to left for(int l = nums.length - 1;l > 0;l --){ if(nums[l] > nums[i]){ j = l; break; } } //Swap nums[i] and nums[j] int swap = nums[i]; nums[i] = nums[j]; nums[j] = swap; //Reverse the sub array from i + 1 (or 0) to nums.length - 1 int n = 0; if(i == 0 && j == 0){ n = 0; }else{ n = i + 1; } int m = nums.length - 1; while(n < m){ int temp = nums[n]; nums[n] = nums[m]; nums[m] = temp; m --; n ++; } } }

Python 代碼：Accepted

class Solution(object):
    def nextPermutation(self, nums):
        
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        
         
        i for the first index nums[k] > nums[k + 1] from right to left
        j for the first index nums[i] < nums[j] from right to left
        
        i = j = 0

        #To find the the first index nums[k] > nums[k + 1] from right to left
        k = len(nums) - 2
        while(k > 0):
            if(nums[k] < nums[k + 1]):
                i = k
                break
            k -= 1

        #To find the the first index nums[i] < nums[j] from right to left
        k = len(nums) - 1
        while(k > 0):
            if(nums[k] > nums[i]):
                j = k
                break;
            k -= 1
        #Swap nums[i] and nums[j]    
        nums[i],nums[j] = nums[j],nums[i]

        #Reverse elements for i + 1(or 0) to len(nums) - 1
        if(i == 0 and j == 0):
            n = 0
        else:
            n = i + 1
        m = len(nums) - 1

        while(n <= m):
            nums[n],nums[m] = nums[m],nums[n]
            n += 1
            m -= 1