@@ -0,0 +1,2618 @@
+// Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.%0A%0A// If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).%0A%0A// The replacement must be in-place, do not allocate extra memory.%0A%0A// Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.%0A// 1,2,3 %E2%86%92 1,3,2%0A// 3,2,1 %E2%86%92 1,2,3%0A// 1,1,5 %E2%86%92 1,5,1%0A%0Apublic class Solution %7B%0A    // This problem is more clearly illustrated by drawing a histogram of input %0A    // array.%0A    // 'next': means smallest number that is greater than the current number.%0A    // The idea is that find a couple such that voilates the increasing order(from end to head of array),%0A    // that is left elemnt smaller than right element, swap them would produce a greater number, %0A    // but not the smallest one, we have to reverse all the numbers on right of left element(which maintain the increasing property, left greater%0A    // than right), this number would be the possible smallest permutation that is greater than original number.%0A    // Last question here is that which left and right index to pick? We pick such couple that left index is largest one(the digit %0A    // which has the least weight) --%3E to maintains that we get next greater number as small as possible. %0A    public void nextPermutation(int%5B%5D num) %7B%0A         int len = num.length;%0A%0A        if(len %3C= 1) return;%0A%0A        int left = Integer.MIN_VALUE;%0A        int right = 0;%0A%0A        for(int r = len - 1; r %3E 0; r--)%7B%0A            for(int l = r - 1; l %3E= 0; l--)%7B%0A                if(num%5Bl%5D %3C num%5Br%5D)%7B%0A                    if(left == Integer.MIN_VALUE)%7B%0A                        left = l;%0A                        right = r;%0A                        continue;%0A                    %7D%0A                    if(l %3E left)%7B%0A                        left = l;%0A                        right = r;%0A                    %7D%0A                %7D%0A            %7D%0A        %7D%0A%0A        if(left != Integer.MIN_VALUE)%7B%0A            //swap left and right then revse the rest.%0A            int l = num%5Bleft%5D;%0A            num%5Bleft%5D = num%5Bright%5D;%0A            num%5Bright%5D = l;%0A            reverse(num, left + 1);%0A        %7Delse%7B%0A            reverse(num, 0);%0A        %7D%0A    %7D%0A%0A    public void reverse(int%5B%5D num,int start)%7B%0A        for(int i=start;i%3C=num.length-1-i+start;i++)%7B%0A            int temp = num%5Bi%5D;%0A            int k = num.length-1-i+start;%0A            num%5Bi%5D = num%5Bk%5D;%0A            num%5Bk%5D = temp;%0A        %7D%0A        %0A    %7D%0A%7D%0A%0A// 4354%0A// 4534%0A// 4435%0A%0A%0A%0A// 4354%0A// 4453%0A// 4435%0A%0A

add next permutation