Next Permutation

Next Permutation

---

今天是一道题目，来自LeetCode#31，难度为Medium，Acceptance为25.2%。

题目如下

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

解题思路及代码见阅读原文

回复0000查看更多题目

今天这一题的解题思路我不打算写了，因为有一个博客写的实在是太好了，转发在这里，原文见http://www.cnblogs.com/devymex/archive/2010/08/17/1801122.html

代码如下

java版

public class Solution {
    public void nextPermutation(int[] nums) {
        if(null == nums || nums.length < 2)
            return;
        int i = nums.length - 1;
        for(; i > 0; i--) {
            if(nums[i - 1] < nums[i])
                break;
        }
        if(i == 0) {
            reverse(nums, 0, nums.length - 1);
            return;
        }
        i--;
        int j = i + 1;
        for(; j < nums.length; j++) {
            if(nums[j] <= nums[i])
                break;
        }
        swap(nums, i, j - 1);
        reverse(nums, i + 1, nums.length - 1);
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    private void reverse(int[] nums, int start, int end) {
        while(start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}