It's not easy to find a rule for this question.
And I think the example is not good.
=> 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:
=>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;
You mentioned that 1243 => 1342, which I think suppose to be 1243 =>1324. The right part also need to be sorted here, right?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.