Question: http://oj.leetcode.com/problems/next-permutation/
Question Name: Next Permutation
This problem seems like a mathematic question, rather than a programming challenge.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | class Solution: # @param num, a list of integer # @return a list of integer def nextPermutation(self, num): # In the greatest permutation of numbers, any number is larger # than or equal to the right remaining numbers. # If the num is not the greatest permutation, there must be # one or more pairs being rule breakers. That is, in these pairs, # the left hand number is smaller than the right hand one. # Search from rightmost to leftmost to find out the least # significant rule breaker. back = len(num) - 2 while back >= 0: front = len(num) - 1 while front > back : if num[back] < num[front]: # Rule breaker found. num[back], num[front] = num[front], num[back] num[back+1:] = sorted(num[back+1:]) return num else: front -= 1 back -= 1 # No rule breaker in this array. Return the lowest possible order. num.sort() return num |
How’s my Python? 🙂