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 and use only constant 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

解法：

简而言之，这道题的意思就是寻找下一个字典序的全排列，所谓字典序，就是从小到大的顺序。算法思路如下：以1，2，4，3，1为例：

因为是找递增的下一个排列，所以从后往前找到第一个升序对的位置，如1,2,4,3,1，从后向前找就是2,4,3,1，因为2比前一个数4小，所以就锁定2这个数。之后就是在4,3,1中找到比2大的最小的那个数3，将3与2对换得到降序排列4,2,1.然后就是将4,2,1反序得到1,2,4.最终结果就是1,3,1,2,4。

代码如下：

class  {
    public void nextPermutation(int[] nums) {
        int rear = nums.length - 1;
        if (rear == -1) {
            return;
        }
        for (int i = rear - 1; i >= 0; i--) {
            int j = i + 1;
            if (nums[i] < nums[j]) {
                int min = 999999999;
                int exchangeindex = i;
                for (int ii = j; ii <= rear; ii++) {
                    int minus = nums[ii] - nums[i];
                    if (min > minus && minus > 0) {
                        min = minus;
                        exchangeindex = ii;
                    }
                }
                int l = nums[i];
                nums[i] = nums[exchangeindex];
                nums[exchangeindex] = l;
                sort(nums, j, rear);
                return;
            }
        }
        for (int i = 0; i <= rear; i++) {
            int j = rear - i;
            if (i >= j) {
                break;
            }
            int l = nums[i];
            nums[i] = nums[j];
            nums[j] = l;
        }
        return;
    }

    void sort(int[] array, int start, int end) {
        for (int i = start; i <= end; i++) {
            int x = array[i];
            int j = i - 1;
            while (j >= start) {
                if (array[j] > x) {
                    array[j + 1] = array[j];
                    j -= 1;
                } else {
                    break;
                }
            }
            array[j + 1] = x;
        }
    }
}

leetcode(31) next permutation 解法：

解法：

近期文章

近期评论

标签

热门

文章归档

分类目录

功能