首页 > 代码库 > LeetCode 31 Next Permutation（下一个全排列）
LeetCode 31 Next Permutation（下一个全排列）
题目链接： https://leetcode.com/problems/next-permutation/?tab=Description
Problem ：寻找给定int数组的下一个全排列（要求：be in-place）
倒序查找到该数组中第一个满足后面的数字大于前面的数字的下标i (当前下标 i 指向 后面的那个比较大的数)
参考代码：
package leetcode_50;/*** * * @author pengfei_zheng * 下一个全排列 */public class Solution31 { public static void nextPermutation(int[] nums) { int len = nums.length; if(len<=1) return; int i = len - 1; for(;i>=1;i--){//从后先前遍历 if(nums[i]>nums[i-1]){ //找到第一个后面的数字大于相邻的前面的那个数的下标 （此时下标指向较大的那个数字） break; } } if(i!=0){ swap(nums,i-1);//从后向前遍历，交换第一个大于index=i-1的那个数 } reserver(nums,i);//将从下标i开始的数组进行从小到大的排序 } private static void swap(int[] nums, int i) { for(int j=nums.length-1;j>i;j--){//从后向前遍历 if(nums[j]>nums[i]){ int t = nums[j]; nums[j]=nums[i]; nums[i]=t; break;//交换第一个比前面的index=i-1的那个数 } } } //从下标i开始到nums.length-1结束，实现从小到大排列 private static void reserver(int[] nums, int i) { int first = i; int last = nums.length-1; while(first<last){ int t = nums[first]; nums[first]=nums[last]; nums[last]=t; first++; last--; } } public static void main(String[]args){ //int []nums={6,3,4,9,8,7,1}; int []nums={1,2,4,3}; nextPermutation(nums); for(int n:nums){ System.out.print(n+" "); } }}
LeetCode 31 Next Permutation（下一个全排列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。