Share my python code, and explain how to get the solution.


  • 3
    L

    It's not easy to find a rule for this question.

    And I think the example is not good.

    Examples here:

    1243
    => 12 43 (2 is the first num who is less than the next), and the num split to two parts, left: [1,2], right: [4,3]

    => 13 42 (swap 2 with 3, because 3 is the first num greater than 2).

    => 13 24 sort right. 13, 42 sorted to 24.

    => 1324 merge left, right.

    Another more complex example:
    1342
    =>13 42 split to left: 13 right: 42 (3 is the first num less than next);

    =>14 32 swap 3 and 4, because in the right part, 4 is the first num greater than 3, from right ->left scan.

    =>14 23 sort right part, (That's why we need to sort the right part).

    =>1423 merge them

    class Solution:
    # @param num, a list of integer
    # @return a list of integer
    def nextPermutation(self, num):
        if(len(num)<=1):return num;
        else:
            splitIdx=-1;
            for i in range(len(num)-2,-1,-1):
                if(num[i]<num[i+1]):
                    splitIdx=i;
                    break;
            replaceIdx=len(num)-1;
            while(replaceIdx > splitIdx):
                if(num[replaceIdx]>num[splitIdx]):
                    break;
                replaceIdx-=1;
    
            num[replaceIdx],num[splitIdx]=num[splitIdx],num[replaceIdx];
            
            right=num[splitIdx+1:];
            right=sorted(right);            
            return num[0:splitIdx+1]+right;

  • 0
    G

    You mentioned that 1243 => 1342, which I think suppose to be 1243 =>1324. The right part also need to be sorted here, right?


  • 0
    L

    yes, my misake, thanks. I refined it.


  • -1
    Z

    Oh, seems to find a person who is use the same way with me


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.