# Sharing my clean and easy-understand java code with explanation

• ``````public class Solution {
public void nextPermutation(int[] nums) {
if(nums.length<=1){
return;
}

int i= nums.length-1;

for(;i>=1;i--){

if(nums[i]>nums[i-1]){ //find first number which is smaller than it's after number
break;
}
}

if(i!=0){
swap(nums,i-1); //if the number exist,which means that the nums not like{5,4,3,2,1}
}

reverse(nums,i);
}

private void swap(int[] a,int i){
for(int j = a.length-1;j>i;j--){
if(a[j]>a[i]){
int t = a[j];
a[j] = a[i];
a[i] = t;
break;
}
}
}

private void reverse(int[] a,int i){//reverse the number after the number we have found
int first = i;
int last = a.length-1;
while(first<last){
int t = a[first];
a[first] = a[last];
a[last] = t;
first ++;
last --;
}
}

}
``````

在当前序列中，从尾端往前寻找两个相邻元素，前一个记为first，后一个记为second，并且满足first 小于 second。然后再从尾端寻找另一个元素number，如果满足first 小于number，即将第first个元素与number元素对调，并将second元素之后（包括second）的所有元素颠倒排序，即求出下一个序列

example:
6，3，4，9，8，7，1
此时 first ＝ 4，second = 9
从尾巴到前找到第一个大于first的数字，就是7
交换4和7，即上面的swap函数，此时序列变成6，3，7，9，8，4，1
再将second＝9以及以后的序列重新排序，让其从小到大排序，使得整体最小，即reverse一下（因为此时肯定是递减序列）
得到最终的结果：6，3，7，1，4，8，9

• It's real an easy understand solution

• tai ji zhi le 66666

• Based on your explanation, I wrote a cleaner code. Thanks for sharing!

``````public class Solution {
public void nextPermutation(int[] nums) {
// find two adjacent elements, n[i-1] < n[i]
int i = nums.length - 1;
for (; i > 0; i --) {
if (nums[i] > nums[i-1]) {
break;
}
}
if (i != 0) {
// swap (i-1, x), where x is index of the smallest number in [i, n)
int x = nums.length - 1;
for (; x >= i; x --) {
if (nums[x] > nums[i-1]) {
break;
}
}
swap(nums, i - 1, x);
}
reverse(nums, i, nums.length - 1);
}

void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
// reverse a[i, j]
void reverse(int[] a, int i, int j) {
for (; i < j; i ++, j --) {
swap(a, i, j);
}
}
}``````

• Good explanation!

• The example is really good for understanding the algorithm. Just translate it to English version for your reference.

``````[6，3，4，9，8，7，1]
i-1 i    k
``````

(1) leftward find the first decreasing number @ index `i - 1`, (`4`)
(2) then nums[i:] must be rightward decreasing (`9,8,7,1`)
(3) leftward find the first number that is larger than `i - 1`, which is at k, (`7`)
(4) swap `i - 1` with `k`, (`6,3,7,9,8,4,1`). we can see that nums[i:] will still be rightward decreasing (`9,8,4,1`)
(5) But we need them to be rightward increasing so that it's the smallest after swapping, so we reversed nums[i:], which get the result (`6,3,7,1,4,8,9`)

• 666666666666666666

• I think this problem will make people misunderstanding,for example,if the input
is [1,321,64],then I think the 'lexicographically next greater permutation' should be [1,64,321],but your algorithm result is [64,1,321].am I think wrong?@sunnyChen18

• 666 !!!you are legendary!!

• @leetcodeLeon
The next lexicographical permutation of [1, 321, 64] is [64, 1, 321]. If you read Lexicographical order Wikipedia page carefully, you will understand.

• If you share a solution, please also share the reasoning behind it. Thanks.

• clever solution!

• @sunnyChen18 Good algorithm!

• @hukun01 agree, it's clearer to break out the "swap with smallest element greater than new element" part.

``````    public void NextPermutation(int[] nums)
{
if (nums == null || nums.Length < 2) return;

// from end backwards - find last elem where sequence is equal or increasing
int head = nums.Length - 1;

{
// we need to incorporate the next elem to further the sequence
// swap the new element with the smallest element in the sequence that is larger than the new element
}

// reverse chars from the head to end of sequence
// this will give the lowest permutation with this head
}

public void Reverse(int[] nums, int i, int j)
{
for (; i < j; i++, j--) Swap(nums, i, j);
}

public void Swap(int[] nums, int i, int j)
{
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
``````

• 太给力。支持大神。这种题真是费脑子。不知道po多久想出来的

• @sunnyChen18 Nice solution. A slight improvement is to use binary search after locating the 'first' element. Time would still be O(n) though.

• you explanation helps me, thanks

• @Lanzevasar You are welcome!

• I have to say: 6 fly!

• 66666666666666

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.