首页 > 代码库 > Leetcode Next Permutation

Leetcode Next Permutation

2024-11-24 01:56:02   202人阅读

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

对于这道题，题意为找出比当前这个排列组合大的组合中的最小的那一个。方法步骤如下:

1.从后往前找，找出第一个不是升序排列的那一个元素，位置记为i，作为特殊元素

2.找出从i开始到len-1元素中比这个特殊元素大的元素中的最小的那一个，二者交换位置

3.从i到len-1，按升序排列

 1 package Next.Permutation; 2  3 import java.util.Arrays; 4  5 public class NextPermutation { 6 public void nextPermutation(int[] num) { 7    int len=num.length; 8    if(len==2){ 9       if(num[0]<num[1]){10           int temp=num[0];11           num[0]=num[1];12           num[1]=temp;13       } 14       return;15    }16    //从后往前找第一个不是单调递增的数字17    int exIndex=-1;18    for(int i=len-1;i>0;i--){19        if(num[i-1]<num[i]){20            exIndex=i-1;21            break;22        }23    }24    //倒序排列，没有比这个更大了，因此需要找出最小的排列，及正序牌系列25    if(exIndex==-1){26        Arrays.sort(num);27    }else{28        //找出从异常位置点的下一个开始到len-1的元素中最小的29        int min=Integer.MAX_VALUE;30        int minIndex=-1;31        for(int i=exIndex+1;i<len;i++){32            if(num[i]<min&&num[i]>num[exIndex]){33                min=num[i];34                minIndex=i;35            }36        }37        //交换异常位置的元素和这个最小的元素38        num[minIndex]=num[exIndex];39        num[exIndex]=min;40        //将异常元素位置后的元素按升序排列41        for(int i=exIndex+1;i<len;i++){42            for(int j=exIndex+2;j<len;j++){43             if(num[j]<num[j-1]){44                 int temp=num[j];45                 num[j]=num[j-1];46                 num[j-1]=temp;47             }   48            }49        }50        51    }52 }53 54     /**55      * @param args56      */57     public static void main(String[] args) {58         // TODO Auto-generated method stub59       int []num={2,3,1};60       NextPermutation service=new NextPermutation();61       service.nextPermutation(num);62       for(int a:num){63           System.out.println(a);64       }65     }66 67 }

 

Leetcode Next Permutation


联系
我们