class Solution: # @param num, a list of integer """ 1, Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation. 2, Find the largest index l greater than k such that a[k] < a[l]. 3, Swap the value of a[k] with that of a[l]. 4, Reverse the sequence from a[k + 1] up to and including the final element a[n]. """ def nextPermutation(self, num): n = len(num) k=-1 for i in range(n-1): if (num[i]<num[i+1]): k=i if k==-1: num = sorted(num) return l = k for i in range(k+1, n): if (num[i] > num[k]): l = i num[k], num[l] = num[l], num[k] tailNum = num[k+1:] tailNum.reverse() num = num[:k+1] + tailNum
this works well in my computer for the tests such as [1, 2], [3, 2, 1], but not in leetcode. When I write the reverse() myself rather than using the python default one, it works with [1, 2]. but not for [3, 2, 1], it seems that the function sorted() does not work neither
sorted() will make a copy of the list (use extra space), which is against the definition of the problem.
tailNum = num[k+1:] will make a copy of the sliced list, which again is against the rule.
The following code will make things clear for you:
a = [1,2,3,4,5] b = a[:4] print b b.reverse() print b print a