【Leetcode】Next Permutation

发布时间：2020-12-13 21:09:11 所属栏目：PHP教程来源：网络整理

导读：题目链接：https://leetcode.com/problems/next-permutation/ 题目： Implement next permutation,which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible,it must rearrange it a

题目链接：https://leetcode.com/problems/next-permutation/

题目：

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 → 3,1 → →




思路：

见注释。。。。

算法：

public void nextPermutation(int[] nums) {  
    int pos = ⑴;  
    // 找到最后1个升序位置  
    for (int i = nums.length - 1; i >= 1; i--) {  
        if (nums[i] > nums[i - 1]) {  
            pos = i - 1;  
            break;  
        }  
    }  
    // 如果没有升序 如3 2 1 需要反转为1 2 3  
    if (pos < 0) {  
        nums = reverse(nums,nums.length - 1);  
        return;  
    }  
  
    // 存在升序 找到pos以后最后1个大于pos的位置  
    // 举例 如1 2 5 4 3 1下1个排列应当是 1 3 1 2 4 5，  
    // 首先定位pos元素为2；找到元素3；二者交换：1 3 5 4 2 1；将5~1反转；  
    for (int i = nums.length - 1; i > pos; i--) {  
        if (nums[i] > nums[pos]) {  
            int tmp = nums[i];  
            nums[i] = nums[pos];  
            nums[pos] = tmp;  
            break;  
        }  
    }  
    // 将pos以后元素全部反转  
    nums = reverse(nums,pos + 1,nums.length - 1);  
}  
  
public int[] reverse(int nums[],int start,int end) {  
    while (start < end) {  
        int tmp = nums[start];  
        nums[start] = nums[end];  
        nums[end] = tmp;  
        start++;  
        end--;  
    }  
    return nums;  
}  






   
                        （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!